A First Taste of Algorithms · The Greedy Idea
The strategy, named
The instinct — build the answer one piece at a time, and at each step grab whatever looks best right now, and never reconsider — is called greedy. It is not a single algorithm; it is a strategy for designing algorithms, a template. Point it at a problem and it proposes a procedure instantly: decide what “looks best” means, then grab repeatedly.
Chapter 1 gave you one clever algorithm, fitted to one problem by hand. Greedy is more ambitious — a machine for generating algorithms — and it generates them cheaply: one pass through your options, one decision per step, no memory of roads not taken, no agonizing. Of the two questions this book asks of everything, greedy aces what does it cost? before you’ve even checked whether it works. That cheapness is the seduction.
But “grab whatever looks best” is only a strategy once you say what best means — and the Saturday just taught you that the choice of “best” is the whole game. “Earliest-starting” is one definition of best, and it failed. So the real question of greedy is never whether to be greedy; it is greedy about what? Get that right and the strategy is perfect. Get it wrong and it misses half your Saturday with a straight face.
So let’s hunt for the right definition of best — the honest way, by trying the plausible ones and watching them fail until one survives.
Three definitions of “best,” two of them wrong
Best = starts earliest. Already dead. The robotics build starts as early as the run but holds you hostage for four hours. Starting early tells you nothing about when you’re free again, and being free again is what lets you do the next thing.
Best = shortest. A sharper idea — short things block less of your day, so grab the shortest available thing each time, then the shortest of what’s left. This feels right. It is wrong, and here is the smallest possible proof, just three events:
A runs 1:00–5:00. B runs 4:00–6:00. C runs 5:00–9:00.
Figure 2.2 — Shortest-first’s defeat: the short event B touches both A and C; grabbing it yields one where skipping it yields two.
B is the shortest (two hours). Grab it greedily and you’ve knocked out both A and C — B overlaps the tail of A and the head of C — so you attend one thing. But skip the tempting short one and take A and C, which don’t overlap each other, and you attend two. Shortest-first measured the event itself and ignored what the event touches. A short thing wedged between two others can be more destructive than a long thing off in the corner.
Best = finishes earliest. Now think about what actually went wrong in both failures. The robotics build was bad because it kept you busy late. B was bad because it straddled two slots. In both cases the damage was about when you become available again. So make availability the whole criterion: always do the thing that finishes soonest among the things you can still attend. Finishing early keeps the most future open — of everything you could do next, the earliest-finisher leaves the largest runway for everything after.
Run it on the Saturday. The run finishes first (10:00) — take it. Among things starting at 10:00 or later, setup finishes first (11:00) — take it. Then the match (12:00), the lunch shift (1:00), study group (2:00), the party (4:00), the movie (5:00). Seven things. The pencil’s answer, produced by a rule.
Figure 2.1 — The overbooked Saturday three ways: the eight events; earliest-start grabbing the all-morning build and salvaging four; earliest-finish fitting seven.
Earliest-finish-first. It is not what anyone reaches for — it feels almost backward, choosing by when things end rather than when they start or how long they take — and that is exactly why it had to be discovered rather than assumed. The obvious rule was obvious and wrong. The right rule is strange and right. That is the texture of greedy: the strategy is simple, but which greedy is the entire problem, and the answer is often counterintuitive.
(One more plausible rule deserves a mention because it’s so tempting: best = fewest conflicts, grab the thing that bumps into the fewest others, avoid the troublemakers. It also fails — Problem 3.3 has a verified case where it gets 2 where earliest-finish gets 4 — and for the same reason: “how many things you conflict with” still isn’t “when you free up.”)
All 32 chapters of A First Taste of Algorithms · Foundations · All courses