16.5 A task-scheduling problem as a matroid

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

$$ \begin 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 $$

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