Greedy algorithms — and when the locally best choice isn't enough

A greedy algorithm builds a solution one step at a time, always picking whatever looks best right now, and never reconsidering that choice later. This is the opposite of dynamic programming's approach (from its own lesson): DP explores multiple possibilities and keeps whichever subproblem results actually lead to the best overall answer; greedy commits immediately to the locally-best option and moves on, never backtracking to check whether an earlier choice was actually a mistake.

Given US coin denominations, always taking the largest coin that fits happens to produce the true minimum number of coins, every time — greedily grabbing the biggest coin at each step never leads to a worse overall answer than some smarter alternative would have found. This works because of a specific property of this particular set of denominations (each is a large enough multiple of the ones below it) — it is not a general fact about "making change" as a problem.

With denominations [1, 3, 4], greedily grabbing the largest coin that fits (4) leaves 2, which then greedily takes two 1s — three coins total. But 3 + 3 = 6 uses only two coins, and there was no way for the greedy approach to discover that, because taking the 4 first was locally correct (it's the largest coin that fits) while being globally wrong. This is the entire danger of greedy: it can look completely reasonable at every single step and still land on the wrong final answer, with nothing about the algorithm's own execution ever signaling that it went wrong.

Given a set of activities each with a start and end time, and one resource that can only host one at a time, always picking the activity that ends earliest among the remaining valid options is provably optimal — it leaves the most possible room for future activities, since no other valid choice could free up the resource any sooner. Unlike the [1, 3, 4] coin problem, this greedy strategy is mathematically guaranteed correct for every possible input, not just a lucky-case coincidence — the proof (an "exchange argument": any optimal solution can be modified to include the earliest-ending activity without making it worse) is exactly what separates a greedy algorithm that's always right from one that merely often looks right.

Both are legitimate, useful algorithmic strategies — the actual skill is recognizing which shape a given problem has, before reaching for one. A common, real mistake is assuming greedy always needs to be proven wrong through testing ("let me just try it and see") — the correct approach is proving (or finding a known reference for) whether the problem has the specific structural property that makes locally-optimal choices compose into a globally-optimal one, the same exchange-argument style of reasoning behind the activity-selection example.

The pattern across all of them: each one has a specific, provable reason the greedy choice never needs revisiting — that proof is the actual content of "this greedy algorithm works," not just an observation that it happened to work on a few test cases.