Greedy algorithms and exchange arguments

Why it matters

Greedy solutions are short and fast, but a rule that feels right is wrong surprisingly often. That makes greedy problems a good probe of reasoning: an interviewer wants to hear why the rule is safe, not only see that it passes the examples. Real systems use greedy decisions everywhere (Huffman coding, Kruskal's and Prim's spanning trees, scheduling and packing heuristics), and knowing when a greedy choice is provably optimal versus merely good is valuable engineering judgement.

Core ideas

A greedy algorithm needs two properties. Greedy choice: some optimal solution contains the first greedy choice. Optimal substructure: after that choice, what remains is a smaller instance of the same problem. Together they give an induction: the first choice is safe, and the remainder is again solved greedily.

Exchange argument, worked sketch. Interval scheduling asks for the largest set of pairwise non-overlapping intervals. Rule: sort by end time and take each interval that starts at or after the end of the last one taken.

1. Let g be the interval with the earliest end. Take any optimal solution O and let o be its interval with the earliest end.
2. Replace o with g. Every other interval in O starts at or after o ends, and g ends no later than o, so the new set is still non-overlapping and has the same size. Hence some optimal solution contains g.
3. Remove g and every interval overlapping it. What remains is the same problem on a smaller input, and induction finishes the proof.

The general recipe: take an optimal solution that first differs from greedy at some step, swap in the greedy choice, and show the result is still feasible and no worse.

Greedy stays ahead. Show by induction that after each step, greedy's partial solution is at least as good as any other solution's after the same number of steps. For jump-style reachability the invariant is the farthest index reachable from the positions scanned so far; for the minimum number of jumps, scanning in BFS-like layers keeps greedy's reach after k jumps at least that of any strategy.

Counterexamples are part of the method. For interval scheduling, earliest start fails when one long interval covers two short disjoint ones, and shortest-first fails when a short interval overlaps two disjoint longer ones. For coin change, largest-coin-first is optimal for systems such as 1, 5, 10, 25 but not in general: with coins 1, 3 and 4 and target 6 it uses 4 + 1 + 1 instead of 3 + 3. Spend a couple of minutes trying to break a rule on tiny inputs before committing to it.

When greedy fails, think DP. Weighted interval scheduling, 0/1 knapsack and general coin change have choices that interact, so a local rule cannot account for what it gives up; dynamic programming over sorted order or over capacity fixes this. Fractional knapsack, by contrast, is greedy by value per unit weight because items can be split.

Implementation shape. Most greedy solutions are "sort by a key, then one scan" in O(n log n), or "repeatedly take the best available item from a heap". The key and the tie-breaking are the algorithm, so state them explicitly.

Common misconceptions

• "If it passes the examples, the rule is right." Examples are chosen to be readable, not adversarial. Search for a counterexample, then argue correctness.
• "Interval problems always sort by start." Merging overlaps sorts by start; maximizing compatible intervals or minimizing removals sorts by end. The objective decides the key.
• "An exchange argument shows greedy equals the optimal solution." It shows that some optimal solution can be transformed to agree with greedy without getting worse; the optimum need not be unique.
• "Greedy and DP are unrelated." A greedy algorithm is a DP in which one choice is provably always best, so only one subproblem is solved. When you cannot prove that, fall back to the DP.
• "Largest-first works for coin change." Only for some coin systems; arbitrary denominations need DP.

How to approach it

Propose the rule, then test it immediately against two or three tiny adversarial inputs, saying what you are checking. If it survives, give a short argument in words: "swap the first differing choice for the greedy one; it stays feasible because...; the objective does not get worse because...". Then code the sort-and-scan and state the complexity. Graduate interviews usually accept a convincing informal argument; mid and senior interviews push harder on ties, equal endpoints and empty input, and on what changes when weights are added.