When Greedy Fails

Here's the setup: you need to make change for 30 cents using the fewest coins possible, and the coins available are 1, 15, and 25 cents. The "obviously correct" greedy approach — always take the largest coin that doesn't overshoot — gives 25 + 1 + 1 + 1 + 1 + 1, six coins. The actual best answer is two 15s. Try to say, before reading on, exactly why greedy failed here, and what property of the coin set it depended on.

The trap: greedy looks right until it isn't

Greedy algorithms — always make the choice that looks best right now, never revisit it — are seductive because they're simple to state and, for a real family of problems, provably optimal. The US coin system (1, 5, 10, 25) happens to be one of those friendly cases: greedy change-making always works there. That success trains an unearned intuition that greedy "just works" for making change generally, which is exactly the trap the 15-cent coin exposes: greedy grabbed the 25 because it looked locally efficient, but that single choice made every remaining step expensive, while committing to two 15s upfront was better precisely because it wasn't the biggest available bite.

What decides whether greedy works

The honest answer is: it depends entirely on the structure of the problem, and you can't know without checking (or already knowing the relevant theorem). Two properties usually need to hold for greedy to be provably optimal:

• Greedy choice property: there's always some optimal solution consistent with making the greedy choice first — picking the locally best option never rules out reaching a global optimum.
• Optimal substructure: once the greedy choice is fixed, the remaining problem (on whatever's left) is a smaller instance of the same problem, so optimality can be argued by induction.

The standard way to prove greedy works, when it does, is an exchange argument: take any optimal solution that disagrees with the greedy choice at some step, and show you can swap in the greedy choice without making things worse — which means an optimal solution consistent with greedy always exists. The standard way to show greedy fails is a single clean counterexample, exactly like the 15-cent coin — you don't need a proof that greedy always fails, just one case where it demonstrably does.

Problem	Does naive greedy work?
Making change with US coins (1, 5, 10, 25)	Yes — provably optimal
Making change with coins {1, 15, 25} for 30 cents	No — greedy gives 6 coins, optimal is 2
Interval scheduling: max number of non-overlapping intervals, pick by earliest finish time	Yes — provably optimal
Interval scheduling: pick by earliest start time instead	No — an early-starting long interval can block many short ones
Fractional knapsack (can take partial items)	Yes — take highest value-per-weight first
0/1 knapsack (items are all-or-nothing)	No — a classic counterexample: greedy by value-per-weight can strictly lose to a different combination

The transferable technique

Before presenting a greedy solution in an interview, spend ten seconds trying to break it: construct the smallest, most adversarial input you can think of (an unusual coin denomination, an interval that's long but starts early, an item with high value but crushing weight) and check the greedy rule against it by hand. If it survives a couple of honest attacks and you can sketch why a swap can't improve on it, say so — that's an exchange argument. If it breaks, say that too; noticing your own greedy idea fails, out loud, reads far better in an interview than presenting a broken algorithm with confidence.