Algorithms from zero
Greedy: multiple-choice review
Crux Multiple-choice synthesis across the greedy unit: greedy-choice property, the exchange argument, when greedy beats DP and when it silently fails, and the right sort key for interval problems.
Your altitude — climbing toward senior
ZeroJuniorMiddleSenior
You are at senior altitude — in orbitSix questions that cut across the whole unit. Each one is a decision you make when you reach for greedy in anger — not a definition to recite, but the judgment call of whether a local choice is provably global, and what to do when it is not.
Goal
Confirm you can connect the greedy-choice property, the exchange argument, the sort-key decision for interval problems, and the failure signature of an unsafe greedy — the synthesis the four lessons built toward.
Quiz
Completed
A teammate says greedy passed all 40 of their random tests, so it must be correct for this problem. Why is this reasoning unsound, and what would actually settle it?
Heads-up Random tests sample inputs; they never establish a universal property. Greedy on coins {1,3,4} is optimal for amounts 1 to 5 and only fails at 6 — a small test set sails right past the one failing case.
Heads-up No finite number of tests proves optimality over an infinite input domain. The issue is not sample size but that testing cannot certify a for-all-inputs claim — only a proof can.
Heads-up Whether tests are random or hand-picked is irrelevant to the logic: examples can confirm a bug but can never confirm the absence of a counterexample. Proof or counterexample is the only verdict.
Quiz
Completed
You want the maximum number of non-overlapping meetings in one room. A colleague sorts by shortest duration (small meetings pack tightest). On [0,4], [3,5], [4,8] what does that produce, and why is the key wrong?
Heads-up Shortest-duration takes [3,5] first and is then blocked from both others, giving 1, not 2. The whole point of this counterexample is that it diverges from the optimum.
Heads-up [3,5] overlaps both [0,4] and [4,8], so all three can never coexist. The maximum non-overlapping set here is 2: [0,4] then [4,8].
Heads-up Sorting by start is the key for MERGING intervals, not for maximization. For most-non-overlapping the only provably-optimal key is earliest finish time — duration and start are both wrong.
Quiz
Completed
In the exchange argument for activity selection, you swap the optimum's first job X out and greedy's earliest-finishing job G in. Which single fact makes the swapped schedule still feasible?
Heads-up The argument never assumes equal start times — G can start earlier or later. What matters is the finish ordering G.finish <= X.finish, which is what guarantees later jobs still fit.
Heads-up Nothing is removed except X; the proof must SHOW the remaining jobs still fit, and it does so via G.finish <= X.finish. There is no magic conflict removal.
Heads-up Greedy picks the earliest-FINISHING job, which is often short, not long. Duration is irrelevant; the finish-time inequality is the engine of the swap.
Quiz
Completed
For coin change with denominations {1, 3, 4} and amount 6, greedy returns 4+1+1 = 3 coins while DP returns 3+3 = 2. What does this mismatch tell you about the exchange argument, and what is the correct fallback?
Heads-up Greedy already sorts coins largest-first; the failure is intrinsic to the {1,3,4} denomination set, not the sort. No ordering rescues it — the greedy-choice property genuinely does not hold.
Heads-up Special-casing one input is a patch over a hole, not a fix. {1,3,4} lacks the property structurally and other amounts can fail too. The principled answer is DP, which needs no such property.
Heads-up DP exhaustively minimizes coins and is provably optimal; 3+3 = 2 coins genuinely beats 4+1+1 = 3. Greedy is the one returning the worse answer here.
Quiz
Completed
Across the unit, what is the precise difference between greedy and dynamic programming on the same optimization problem?
Heads-up Greedy explicitly does NOT explore combinations — it commits to one local choice and never compares alternatives. That is exactly why it can be wrong where DP is right, as with coins {1,3,4}.
Heads-up It is the reverse: DP is correct on any problem with optimal substructure; greedy is correct only on the subset that also has the greedy-choice property. Greedy trades correctness range for speed.
Heads-up They can return different results — that is the entire {1,3,4} lesson. The difference is what they explore (all combinations vs one local choice), not recursion style.
Quiz
Completed
In Gas Station, a colleague returns -1 the first time the running tank goes negative at some station i. Why is that wrong, and what is the correct logic?
Heads-up Running dry from one candidate start says nothing about other starts. The trip can still be feasible from a later station; feasibility is decided by the total net fuel, not the first dip.
Heads-up Resetting to start+1 is both slower and based on the wrong invariant: every station between start and i is also disqualified (each was reached with non-negative tank from start, so starting there reaches i with even less fuel). Skip them all — jump to i+1.
Heads-up The first station's local balance is irrelevant to global feasibility. The single condition that decides whether ANY start works is total net fuel >= 0.
Recap
The through-line of the unit is one discipline: a greedy algorithm always runs and always returns something, so the only question that matters is whether its local choice is provably global. The exchange argument (or stays-ahead) is how you prove safety; a missing swap — like coins 4 for 6 — is itself the proof of failure, and your fallback is DP. For interval problems the hard part is the sort key: earliest finish for maximization, start for merging, start-and-end sweep for rooms. And for scan greedies like Gas Station, never decide from a local dip — decide from the global invariant.