Hints — p89 Course Schedule III

  1. Sort courses by deadline ascending. Exchange argument: any feasible schedule can be reordered to respect deadline order without loss.

  2. Walk in deadline order; maintain cur_time (total time committed) and a max-heap of accepted durations.

  3. For each (d, dl): if cur_time + d ≤ dl, accept and push to heap. Else if heap’s max > d, swap: replace the longest accepted with this one, adjusting cur_time -= (max - d).

  4. The swap-out is the key insight: same count, but smaller cur_time ⇒ more room for future courses. Never hurts.

  5. This is classical Moore-Hodgson (1968): minimize late jobs on a single machine with unit weights. Weighted version is NP-hard.

If stuck: see solution.py.