p89 — Course Schedule III

Source: LeetCode 630 · Hard · Topics: Heap, Greedy, Exchange Argument Companies (2024–2025): Google (high), Amazon (medium), Meta (medium) Loop position: The swap-out lemma. Sort by deadline; max-heap of accepted durations; if a new course fits, accept; else if a longer one is already accepted, swap. Proves dramatic mastery of greedy exchange.

1. Quick Context

Given courses [duration, lastDay], you can take at most one course at a time. A course must finish by its lastDay. Maximize the number of courses you can take.

Solution (deadline-sorted swap-out greedy):

  1. Sort courses by lastDay ascending.
  2. Max-heap of accepted durations; track cur_time.
  3. For each (d, dl):
    • If cur_time + d <= dl: accept (push d, cur_time += d).
    • Else if heap and heap_max > d: swap — replace heap_max with d, cur_time -= (heap_max - d).
    • Else skip.

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/course-schedule-iii/

STOP. 35-min timer.

3. Prerequisite Concepts

  • Greedy with rollback / swap (not just monotone accept).
  • Deadline-sorted scheduling (Moore-Hodgson, EDF).
  • Max-heap for “longest committed”.

4. How to Approach (FRAMEWORK 1–9)

1. Restate: Max number of courses; each must finish by its deadline; serial execution.

2. Clarify: Can start at time 0? Yes. All distinct deadlines? No.

3. Examples: [[100,200],[200,1300],[1000,1250],[2000,3200]] → 3.

5. Brute: Sort by deadline; try every subset; check feasibility. Exponential.

6. Target: O(n log n).

7. Pattern: Moore-Hodgson swap-out.

8. Develop: see solution.py.

9. Test: all fit; none fit; chain that requires swap.

5. Progressive Hints

See hints.md.

6. Deeper Insight

6.1 Why sort by deadline?

Exchange argument: suppose OPT has any two courses i, j with dl_i < dl_j but i scheduled after j. Swap them: still feasible (j fits in i’s old slot iff i fit in j’s old slot, both ≤ dl_j). After enough swaps, OPT respects deadline order. So WLOG, schedule in deadline-sorted order.

6.2 The swap-out lemma

Claim: when considering course c with cur_time + d_c > dl_c, if heap_max > d_c, swapping gives same count but smaller cur_time, which never hurts future courses.

Proof:

  • Same count: heap size unchanged.
  • Smaller cur_time: cur_time' = cur_time - (heap_max - d_c) < cur_time.
  • Feasibility of past commitments: all past courses had deadlines ≤ dl_c (sorted); their feasibility was based on cur_time at the time they were scheduled, not now. Removing the max and adding d_c only reduces cur_time ⇒ all past feasibility still holds.

6.3 Why max-heap (longest), not min-heap?

We swap out the longest to free maximum time. Swapping out the shortest gains nothing.

6.4 Moore-Hodgson algorithm — classical reference

This is exactly Moore’s algorithm (1968) for “minimize number of late jobs on a single machine, all weights = 1”. The optimal complement: max number of on-time jobs = total - min late.

6.5 What if weights matter (weighted version)?

Becomes weighted Moore-Hodgson — NP-hard in general. DP on (time, course index) for small inputs.

6.6 Family: deadline-sorted swap-out

  • LC 630 Course Schedule III (this).
  • LC 1834 Single-Threaded CPU (different: minimizing total wait, not max count).
  • LC 502 IPO (different: gating by capital, not deadline).
  • LC 1353 Maximum Number of Events That Can Be Attended (similar deadline pattern).

7. Anti-Pattern Analysis

  1. Sort by duration — fails; deadline order is essential.
  2. Min-heap of durations — swap-out lemma breaks; no gain.
  3. No swap; just skip if doesn’t fit — misses swaps that would yield same count + lower cur_time.
  4. Reset cur_time per swap-out incorrectly — must subtract (heap_max - d_new), not heap_max alone.
  5. Sort by lastDay descending — backward; misses Moore-Hodgson structure.
  6. DP on (time, count) — exponential; works on tiny inputs but signals you missed greedy.

8. Skills & Takeaways

  • Moore-Hodgson swap-out greedy.
  • Deadline-ordered scheduling with rollback.
  • Max-heap for “what to evict”.

9. When to Move On

  • Solve cold in 25 min.
  • State and prove swap-out lemma.
  • Cite Moore-Hodgson by name.

10. Company Context

  • Google: L5/L6; loves swap-out exchange arguments.
  • Amazon: L6.
  • Meta: E5/E6.

Strong: “Moore-Hodgson swap-out: sort by deadline, max-heap, accept-or-swap. Exchange argument: swap-out never hurts count and lowers cur_time. Cited weighted version is NP-hard.”

11. Interviewer’s Lens

SignalJuniorMidSeniorStaff+
Sort keyWrongAfter hintDeadline+ exchange proof
Swap lemmaNoneNoneVerbal+ formal claim
FamilyNoneNoneLC 1353+ Moore-Hodgson reference
NP-hard variantNoneNoneNone+ weighted version

12. Level Delta

  • Mid (L4): Tries duration-sort; fails; corrects with hint.
  • Senior (L5): Cold; verbal swap-out reasoning.
  • Staff (L6): + cites Moore-Hodgson; + weighted NP-hard.
  • Principal (L7+): + LP relaxation of weighted Moore-Hodgson + connection to earliest deadline first (EDF) scheduling theorem in real-time systems.

13. Follow-up Q&A

Q1: Courses can be preempted (resumed later). A1: Preemptive EDF; feasibility check by Liu-Layland utilization bound Σ d_i/dl_i ≤ 1. Different algorithm.

Q2: Multiple machines. A2: Parallel-machine scheduling; NP-hard for m ≥ 2 even with all weights = 1 (m-machine Moore-Hodgson).

Q3: Weighted (each course has a value). A3: NP-hard; DP for small instances; LP relaxation for approximations.

Q4: Online (courses arrive over time). A4: Same swap-out works online — but you can’t “uncommit” time you’ve already spent on a course you’re partway through (depends on preemption model).

Q5: Trace the algorithm on [[5,5],[4,6],[2,6]]. A5: dl-sorted; take 5→cur=5; 4 doesn’t fit (cur+4=9>6) but heap_max=5>4 → swap, cur=4; 2 fits (4+2=6) → take, cur=6. Result: 2 courses ({4-duration, 2-duration}).

14. Solution Walkthrough

See solution.py:

  • schedule_course_greedy — Moore-Hodgson swap-out.
  • schedule_course_brute — try all subsets in deadline order.

15. Beyond the Problem

Principal code review: “Course Schedule III is Moore-Hodgson (1968) in disguise — the canonical ‘minimize late jobs on a single machine, unit weights’ problem. The swap-out lemma is what makes it polynomial; the moment weights enter, the problem becomes NP-hard and you fall back to LP-relaxation rounding or DP for small instances. The Staff+ insight: the swap-out is a localized 1-step rollback that preserves count while improving the state (cur_time). This pattern — ‘reject by swapping out the worst already-accepted’ — recurs in: page-replacement (LRU is a special case of competitive swap-out), caching, online matching with deletion. The lesson scales: whenever your greedy doesn’t have a clean monotone-accept structure, look for a swap-out: ‘is there an already-committed element that, if evicted, would still maintain optimality?’ If yes, the algorithm is O(n log n) with a heap; if no, you’re in NP-hard territory. Real-world analogs: meeting-room reservation with priorities, virtual-machine consolidation in datacenters, scheduling preemptible batch jobs on a fixed CPU budget.”