16.5 A task-scheduling problem as a matroid

16.5-1

Solve the instance of the scheduling problem given in Figure 16.7, but with each penalty \(w_i\) replaced by \(80 - w_i\).

We begin by just greedily constructing the matroid, adding the most costly to leave incomplete tasks first. So, we add tasks \(7, 6, 5, 4, 3\). Then, in order to schedule tasks \(1\) or \(2\) we need to leave incomplete more important tasks. So, our final schedule is \(\langle 5, 3, 4, 6, 7, 1, 2 \rangle\) to have a total penalty of only \(w_1 + w_2 = 30\).

16.5-2

Show how to use property 2 of Lemma 16.12 to determine in time \(O(|A|)\) whether or not a given set \(A\) of tasks is independent.

We provide a pseudocode which grasps main ideas of an algorithm.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

IS-INDEPENDENT(A)
    n = A.length
    let Nts[0..n] be an array filled with 0s
    for each a in A
        if a.deadline >= n
            Nts[n] = Nts[n] + 1
        else
            Nts[d] = Nts[d] + 1
    for i = 1 to n
        Nts[i] = Nts[i] + Nts[i - 1]
    // at this moment, Nts[i] holds value of N_i(A)
    for i = 1 to n
        if Nts[i] > i
            return false
    return true

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用