A First Taste of Algorithms

Chapter 2: The Greedy Idea

✦ ✦ ✦

In which the obvious move is wrong three times before it is right

Too much Saturday

Here is a problem you have actually had. It is Saturday. More things are happening than you can possibly do, and they overlap, so you have to choose. You want to do as many as you can — not the most important, not the most fun, just the largest number of things you can physically fit into the day without being in two places at once.

A real Saturday:

Two things conflict if they overlap in time. (Finishing at 1:00 and starting at 1:00 is fine — you make it across town; call that back-to-back, not a conflict.) The question: what is the most things you can attend?

Try it yourself before reading on. Really — get a pencil, find a combination, then try to beat it. The answer for this particular Saturday is seven (everything except the all-morning robotics build), but finding seven is not the point. The point is the rule you used to find it — because in a minute we are going to discover that the obvious rule is wrong, that the right rule is not obvious at all, and that the gap between those two facts is one of the most powerful ideas in this book.

The obvious rule, and its humiliation

What did you do first? Most people reach for the same instinct: do the thing that starts soonest, then the next thing that starts after that one finishes, and so on. First come, first served. It is how a day naturally feels — handle the morning, then the midday, then the afternoon.

Watch it walk off a cliff. Earliest-starting thing first: the robotics build opens its doors at 8:30, earlier than anything else, so “earliest start” grabs it — and it runs until 1:00. Your whole morning is now gone, because the run, the setup, the match, and the lunch shift all conflict with the build. After it ends at 1:00 you can still catch study group, the party, and the movie. Total: four things. The obvious rule got you four. The pencil got you seven.

Sit with that, because it is the chapter in one stroke. The most natural strategy in the world — the one your hands reach for without being asked — is not slightly suboptimal. It misses almost half the day, and it does so while feeling completely reasonable at every step. “Do the next thing that’s starting” is wrong, and wrong in a way you would never notice without counting.

So the obvious rule fails. What’s the right one? Before we find it, let’s name what we’re doing, because it has a name and the name is worth more than the Saturday.

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