Week 17 — Advanced Greedy & Scheduling
Theme: Heap-driven greedy. Every problem this week reduces to “at each decision point, the heap tells you the right move”. The Staff signal is recognizing the two-heap or sort-then-heap pattern and proving each greedy choice optimal via exchange.
Daily schedule
| Day | Problem | LC # | Difficulty | Key archetype |
|---|---|---|---|---|
| Mon | p86 — Meeting Rooms II | 253 | Medium | Min-heap of end times (or sweep line on events) |
| Tue | p87 — Reorganize String | 767 | Medium | Max-heap of frequencies with cooldown buffer |
| Wed | p88 — IPO | 502 | Hard | Two heaps: min on capital + max on profit — affordability gate |
| Thu | p89 — Course Schedule III | 630 | Hard | Sort by deadline + max-heap swap — counterintuitive exchange |
| Fri | p90 — Single-Threaded CPU | 1834 | Medium-Hard | Sort by enqueue + min-heap of (proc_time, idx) event loop |
Readiness gate (Friday)
- For Meeting Rooms II, derive both the min-heap solution AND the sweep-line solution; explain which is preferable when.
- For Reorganize String, articulate the feasibility condition
max_freq ≤ (n+1)/2and prove it tight. - For IPO, justify why lazy admission (only add affordable projects to max-heap as capital grows) beats sorting.
- For Course Schedule III, state and prove the swap-out lemma: if a course can’t fit, swap with the heap’s longest-duration accepted course iff it’s longer.
- For Single-Threaded CPU, articulate the two-phase event loop: sort by enqueue, advance time when idle, pop heap by (proc_time, idx).
Why these together
These five problems share a structural backbone: scan items in some natural order; at each step, the heap maintains the “best so far” view. The greedy correctness in each comes from a different exchange argument:
- Meeting Rooms II — exchange between rooms is free; only count matters.
- Reorganize String — letters at the top of the heap are the constraint; cooldown buffer prevents same-letter adjacency.
- IPO — affordability is monotone in capital; lazy admission preserves optimality.
- Course Schedule III — counterintuitive: replace a longer accepted course with a shorter incoming one to free up future slack.
- Single-Threaded CPU — the heap simulates the OS scheduler; ordering by (proc_time, idx) is the tie-break rule.
By Friday, the candidate should be able to classify a scheduling problem by “what does the heap hold?” within 60 seconds.