Taking the Best Bite Each Time
A greedy algorithm builds a solution step by step, at each step making the choice that looks locally best — the most immediately beneficial — and never reconsidering. Greedy methods are simple and fast, but their great danger is that a series of locally optimal choices does not always produce a globally optimal result.
Sometimes greedy is provably correct. Making change with standard coin systems, scheduling to minimize lateness, and building a minimum spanning tree (Kruskal's and Prim's algorithms) are cases where the greedy choice is guaranteed optimal, provable via an exchange argument or the theory of matroids. When it works, greedy is wonderfully efficient.
But greedy often fails, and the way to see this is a counterexample. Consider making change for 30 using coins {1, 15, 20}: the greedy "take the largest coin ≤ remaining" picks 20, then needs 10 ones — 11 coins total. But the optimal is two 15s — just 2 coins. The greedy local choice (grab the biggest) led to a globally worse answer. A single counterexample is enough to disprove that a greedy strategy is optimal.
The discipline, then, is: greedy is a tempting first idea, but you must prove it optimal (via an exchange or matroid argument) or find a counterexample that refutes it. Never assume a greedy algorithm is correct just because it is simple and often works.
Common pitfall: assuming that because a greedy choice is locally optimal, the overall result is globally optimal. It frequently is not — as the coin example shows. To trust a greedy algorithm you must prove its correctness; otherwise a single counterexample can demolish it.