A First Taste of Algorithms · The Greedy Idea

The same instinct, somewhere it betrays you

So greedy, pointed correctly, is provably perfect on scheduling. Lulled by that, you might start to trust the instinct — grab the locally best thing — as if it were generally safe. It is not, and the cleanest way to feel the danger is to watch the exact same instinct fail on a problem where it looks even more obviously fine than “earliest start” did.

A problem from a world before your time, which is part of the point. Long ago, people paid for things with metal coins of fixed values, and a cashier making change had to hand back a given amount using as few coins as possible. The greedy rule is the one every old cashier used without thinking: hand over the biggest coin that doesn’t overshoot, then the biggest that fits in what’s left, and so on. For the coins those societies actually used, this works perfectly — it always produces the fewest coins.

Now invent a country. Its mint, for whatever strange reason, makes coins worth exactly 1, 7, and 10. You owe someone 14. Apply the cashier’s instinct: the biggest coin that fits is 10, so hand it over; now you owe 4, and only 1-coins fit, so four of them. Five coins: 10 + 1 + 1 + 1 + 1.

The right answer is two coins: 7 + 7.

Perform the autopsy, because it is the same disease as earliest-start in a new body. The greedy choice was not stupid — 10 was the biggest coin that fit. But grabbing it destroyed a better future greedy never even priced: the 7 + 7 plan was sitting right there, worth less per coin at the first step and worth more in the end. Greedy optimized the step and mortgaged the rest. It is blind in exactly one direction — forward — and it never looks back to notice what it threw away.

Two lessons, and the second is the deep one:

1. The same instinct succeeds on one problem and fails on another. Earliest-finish-first was greedy and perfect; grab-the-biggest-coin is greedy and, in this country, wrong by 150%. So “greedy” is never the answer by itself.
2. Whether greedy works is a property of the problem, not of greed. And you already know the test: does the exchange argument go through? For scheduling it did. Try it here — swap greedy’s 10 into the 7 + 7 plan — and it breaks: 10 + 7 isn’t 14, and patching with 1-coins makes the answer worse. The swap has a cost. That broken swap is the precise, structural reason greedy fails on these coins and succeeds on the Saturday. Not a vibe. A swap that does or doesn’t go through.

File this country’s coins in your head — 14, paid badly with five coins when two would do — because this wound does not heal in this chapter. It is the standing reminder that locally best can mortgage the global future, and it returns, by name, twice more: in Chapter 4, where a method that refuses to commit early finds the 7 + 7 by pricing every option instead of grabbing one; and in Chapter 8, in continuous disguise, when an algorithm walking downhill on a landscape commits its way into the wrong valley for exactly this reason. The coins are not really about coins. They are about the price of not looking back.

Deeper water: how the coins are caught, and how honest coins are certified

“Greedy fails for some amount” looks like a claim needing an infinite search — infinitely many amounts. It isn’t, by a small theorem of Kozen and Zaks: if greedy change ever fails, it already fails at some amount below the sum of the two largest coins. For {1, 7, 10} that bound is 17, and the smallest failure, 14, sits under it. Read the contrapositive, the useful direction: audit every amount below the bound, and if greedy survives all of them, it is correct for all infinitely many amounts forever. Your Lab 2 audit loop on {1, 5, 10, 25} up to 34 is therefore not evidence — it is a proof, a finite certificate of an infinite claim, run by machine. Problem 3.5 has you write it down. (Notice the kind of result: infinity fenced into a finite check — Chapter 1’s lower bound fenced what’s possible; this fences where failure can hide.)

Deeper water: a door, ajar

Scheduling is not a lucky one-off. There is a whole theory — of structures called matroids — characterizing a large family of problems on which greedy is guaranteed optimal, all by essentially the exchange argument you saw. That a single proof shape could be bottled and poured over infinitely many problems is the kind of thing that happens in mathematics more often than seems fair. The door stays ajar; this book does not walk through it.

Where this leaves us

Greedy is a strategy, not a truth. The obvious version of it failed your Saturday by half; a subtler version — earliest-finish-first — was provably perfect; the very same instinct, on a strange country’s coins, failed again. What separated success from failure was never how clever the rule sounded. It was whether the exchange argument went through: whether any other answer could be massaged into greedy’s at no cost. When it can, greedy is unbeatable. When it can’t, greedy lies with total confidence.

And the failures taught more than the success. Which greedy is the whole problem, the right choice is often the counterintuitive one, and “locally best” can quietly bankrupt the future — the coins’ lesson, filed for two later chapters.

And there is a hint of the next chapter hiding in the exchange argument, if you look. After greedy picks the first event — the earliest finisher — what’s left is the same problem on the events that remain: attend the most non-overlapping things from a smaller pile. Pick the earliest finisher of those, and you face a smaller pile again. The problem contains a smaller copy of itself, and greedy is really solving that smaller copy, and the smaller copy inside that, all the way down. That structure — a problem defined in terms of a smaller version of itself — is the engine of the next chapter, and it is stranger and deeper than greedy. Instead of committing to one option at each step and never looking back, you solve a problem by handing a smaller copy of it to yourself.

All 32 chapters of A First Taste of Algorithms · Foundations · All courses