# 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
```