Greedy algorithms: take the best now, never look back

A lecture hall takes bookings for one day, and you want to fit in as many talks as you can, never two at once. With 30 requests there are about a billion sets of talks to check. Or follow one rule: of the talks that still fit, take the one that finishes first, and never change your mind. That rule fits the most talks every time.

It is a greedy algorithm: make the choice that looks best now and never take it back. Looking best is not always being best: in the dynamic programming lesson, the biggest coin first paid out 6 with three coins where two would do. This lesson shows how to tell a safe greedy rule from one that only sounds safe.

greedy choice

The option a fixed rule ranks best right now, such as the activity that finishes first. It is taken at once and never undone.

greedy-choice property

Some best solution starts with the greedy choice: not necessarily every best solution, just one.

optimal substructure

After a choice, what is left is a smaller problem of the same kind, and its best solution completes a best solution.

exchange argument

The usual proof of the greedy-choice property: swap a choice in any best solution for the greedy one, and show the result is still allowed and no worse.

counterexample

One input on which a rule does worse than the best possible. One is enough to prove the rule wrong.

Five activities want one room. A runs from 0 to 10, and B, C, D and E fill the time from 1 to 9 in four short slots.

Sort by start time instead and A goes first, holding the room until 10, by when every other activity has started: one activity. What matters is when an activity finishes, because the one that frees the room soonest leaves the most time for the rest.

That is a hunch; here is the proof. Take any schedule with the most activities, and look at its first activity. B finishes at 3, the earliest of all, so it ends no later than that one. Swap B in. Every other activity in the schedule starts no earlier than the old first one ends, so no earlier than B ends either: no overlaps, and the same count. So some best schedule starts with B, and choosing B loses nothing. What is left is the same problem, smaller: the activities that start at 3 or later. The same argument picks the next choice, and the next, so one pass in finish order is enough, remembering only last, the time the latest choice ends.

The same proof works on another problem. A knapsack holds 50 kg of goods that can be cut, like grain or cloth. The greedy rule: pack the best value per kilo first.

Here the swap is a kilo for a kilo. If a packing holds a kilo of C while some of A is left out, swapping the two keeps the weight and adds 6 − 4 = 2 to the value. So a best packing never leaves a better kilo out while a worse one is in, and that is exactly the packing ratio order makes. Only the last item is ever cut.

Both algorithms sort by the greedy rule, then make one pass that settles each item once and never looks back.

Eleven activities, lettered in order of finish time, so the sort leaves them where they are. A is taken without a question; from B on, predict whether each activity starts no earlier than last, the time the room becomes free.

Four of the eleven fit: A, D, H and K. Each of the seven skipped overlaps the choice made just before it.

Here is the pass as a function, on talks already sorted by finish time, each a title, a start and an end. The variable last starts at 0, so the first talk always fits, and the test start >= last lets a talk start the moment the last one ends.

def choose_talks(talks):
    chosen = []
    last = 0
    for title, start, end in talks:
        if start >= last:
            chosen.append(title)
            last = end
    return chosen

bookings = [['A', 1, 3], ['B', 2, 5], ['C', 4, 6], ['D', 5, 8], ['E', 6, 9], ['F', 8, 10]]
picked = choose_talks(bookings)
print(' '.join(picked))

Earliest finish is not the only rule that sounds right. Shortest first sounds as good: a short activity uses little of the room's time. In the run below, though, the shortest activity, B, clashes with both the others, so that rule fits just one.

The value-per-kilo rule has a limit too. Here it is on three items that can be cut, in a 10 kg knapsack:

Now make them a 6 kg laptop and two 5 kg cameras, which can't be cut. The same rule takes A, and the 4 kg left holds neither camera: 10. Yet B and C weigh exactly 10 kg together and are worth 14.

Not every greedy algorithm can sort once at the start. Dijkstra's algorithm settles the closest unsettled node next, and each node it settles can bring others closer, so a heap hands it each choice in O(log n). Its proof needs edges of non-negative weight: past a negative edge, a settled node could still get closer.

• A greedy algorithm makes the choice that looks best now and never takes it back. It is usually a sort and one pass: O(n log n), with the sort as the cost.
• It is correct only when some best solution starts with the greedy choice and what is left is a smaller problem of the same kind. An exchange argument proves the first; one counterexample proves a rule wrong.
• Activity selection: sort by finish time and take each activity that starts no earlier than the last one taken ends. Earliest start and shortest first both fail on small inputs.
• Fractional knapsack: pack the best value per kilo first, cutting only the last item. For whole items that rule fails, and the 0/1 knapsack needs dynamic programming.
• Next: minimum spanning trees, where the cheapest edge joining two separate pieces is safe for the same kind of reason (try Kruskal's algorithm), and Huffman coding, which keeps merging the two rarest groups of symbols. Practise with Fewest Ranges to Remove, activity selection counted the other way, Reach the Last Index and Drive Once Around a Ring Road, or fool a greedy cashier in Break it.