Week 16 — Greedy Mastery & Exchange Arguments
Theme: Greedy is the most dangerous interview category. The wrong greedy choice produces code that passes 90% of cases and fails silently on the 10% that determine the hire decision. This week trains the exchange argument — the only honest tool for proving a greedy is correct — and contrasts greedy against binary-search-on-answer where they meet in the middle.
Daily schedule
| Day | Problem | LC # | Difficulty | Key archetype |
|---|---|---|---|---|
| Mon | p81 — Queue Reconstruction by Height | 406 | Medium | Sort + insert at index — tallest-first invariant |
| Tue | p82 — Gas Station | 134 | Medium | Prefix-sum greedy — failure-point skip lemma |
| Wed | p83 — Task Scheduler | 621 | Medium | Frequency greedy + slot formula — max-heap simulation vs closed-form |
| Thu | p84 — Min Arrows to Burst Balloons | 452 | Medium | Interval greedy — sort by end, count disjoint |
| Fri | p85 — Split Array Largest Sum | 410 | Hard | Binary-search-on-answer + greedy feasibility — DP↔greedy parity |
Readiness gate (Friday)
- State the exchange argument for sorting tall-first in Queue Reconstruction.
- Prove the “skip past the failure point” lemma for Gas Station (why you never need to restart in the middle).
- Derive the Task Scheduler closed-form
max(n, (max_freq-1)*(n+1) + count_of_max)from the max-heap simulation. - Sort intervals by end (NOT start) for arrow-bursting and explain why start-sort fails.
- For Split Array Largest Sum, articulate the bijection between the DP solution and the binary-search-on-answer solution — why both give the same answer and when each is preferable.
Why these together
These five form the greedy correctness toolkit:
- Queue Reconstruction — exchange argument over a 2D sort key.
- Gas Station — prefix-sum invariant proves no restart is ever beneficial below the failure point.
- Task Scheduler — same problem solved two ways (heap simulation, closed-form), illustrating that recognizing the algebraic structure beats brute simulation.
- Burst Balloons — interval scheduling, the canonical “sort by end” pattern that also underlies activity selection.
- Split Array Largest Sum — bridges greedy (feasibility check) and binary search (parameter search) and contrasts with the O(n²·k) DP. The Staff-level signal is choosing the right tool given constraints.
By Friday, the candidate should be able to prove a greedy correct (not merely test it) and to detect when a problem framed as greedy is actually binary-search-on-answer wearing greedy clothes.