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$.

$$ \begin{array}{c|ccccccc} a_i & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline d_i & 4 & 2 & 4 & 3 & 1 & 4 & 6 \\ w_i & 10 & 20 & 30 & 40 & 50 & 60 & 70 \end{array} $$

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.

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