16.5-1

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

ai1234567di4243146wi10203040506070 \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,37, 6, 5, 4, 3. Then, in order to schedule tasks 11 or 22 we need to leave incomplete more important tasks. So, our final schedule is 5,3,4,6,7,1,2\langle 5, 3, 4, 6, 7, 1, 2 \rangle to have a total penalty of only w1+w2=30w_1 + w_2 = 30.

16.5-2

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

Create an array BB of length nn containing zeros in each entry. For each element aAa \in A, add 11 to B[a.deadline]B[a.deadline]. If B[a.deadline]>a.deadlineB[a.deadline] > a.deadline, return that the set is not independent. Otherwise, continue. If successfully examine every element of AA, return that the set is independent.