Greedy algorithms and when they work
In short: A greedy algorithm takes the best choice at each step and never goes back; it gives the optimal answer only on problems where that choice is safe, which needs a proof such as the exchange argument.
Problem
The meeting room
The coworking space has one meeting room. Eight requests have come in for tomorrow, each with a start and an end hour. Two meetings that overlap cannot be in the room at the same time. You want to accept as many teams as possible: every team you turn down goes to the competition.
The first ideas are simple rules: the earliest request first, or the shortest first (shorter ones take less time). You sort by the rule and accept every request that does not overlap the ones already accepted:
def book(requests, rule): taken = [] for start, end in sorted(requests, key=rule): if all(end <= s or e <= start for s, e in taken): taken.append((start, end)) return taken
def show(rule, taken): slots = ", ".join(f"{s}–{e}" for s, e in taken) print(f"{rule}: {slots} ({len(taken)})")show("By start", book(requests, lambda r: r[0]))show("By length", book(requests, lambda r: r[1] - r[0]))show("By end", book(requests, lambda r: r[1]))By start: 8–16, 17–20 (2)By length: 11–13, 14–16, 18–20 (3)By end: 9–12, 12–15, 15–18, 18–20 (4)By start gives 2 meetings, by length 3, and by end 4. Is 4 the most? Try all 2⁸ = 256 subsets: yes, 5 do not fit. But why exactly the rule "by end", and how can you be sure without trying everything?
The idea
A greedy algorithm
A greedy algorithm makes the choice that looks best now and never comes back to reconsider it. There is no table as in dynamic programming and no trying of every possibility: usually one sort and one pass.
For the room, greedy is: sort the requests by end and accept every one that starts no earlier than the moment the room becomes free. One variable, freeFrom, keeps that moment, so you do not have to compare with every meeting already accepted.
The three rules from the problem are all greedy. The difference is what they count as "best now", and only one of them is right. Greedy is fast and simple, but it comes without a guarantee: every greedy rule needs an argument that the choice at the moment does not spoil the future.
See it
Greedy by end
def max_meetings(requests): taken = [] free_from = 0 for start, end in sorted(requests, key=lambda r: r[1]): if start >= free_from: taken.append((start, end)) free_from = end return takensorted(..., key=lambda r: r[1]) gives a new list sorted by end, and start, end unpacks each pair.requests = [ (8, 16), (12, 15), (9, 12), (15, 18), (11, 13), (17, 20), (14, 16), (18, 20),]taken = max_meetings(requests)for start, end in taken: print(f"{start}–{end}")print(f"Meetings: {len(taken)}")9–1212–1515–1818–20Meetings: 4def max_meetings(requests): taken = [] free_from = 0 for start, end in sorted(requests, key=lambda r: r[1]): if start >= free_from: taken.append((start, end)) free_from = end return takenStep by step, in words
- Eight requests for one meeting room, in the order they came in. Sort them by end: first is the one that ends earliest.
- The orange line is where the room becomes free. At the start nothing is booked: free from 0.
- Request 1 (9–12) starts at 9, the room is free from 0: take it. Now the room is busy until 12.
- Request 2 (11–13) starts at 11, before 12: it overlaps a meeting already taken, decline it.
- Request 3 (12–15) starts at 12, the room is free from 12: take it. Now the room is busy until 15.
- Request 4 (8–16) starts at 8, before 15: it overlaps a meeting already taken, decline it.
- Request 5 (14–16) starts at 14, before 15: it overlaps a meeting already taken, decline it.
- Request 6 (15–18) starts at 15, the room is free from 15: take it. Now the room is busy until 18.
- Request 7 (17–20) starts at 17, before 18: it overlaps a meeting already taken, decline it.
- Request 8 (18–20) starts at 18, the room is free from 18: take it. Now the room is busy until 20.
- 4 meetings: 9–12, 12–15, 15–18, 18–20. Each one taken ends the earliest of the rest, so it leaves the most of the day for the others.
Every meeting accepted leaves the room free as early as possible. The declined ones are no loss: each of them overlaps a meeting that ends no later than it does.
More precisely, if you are curious
If two requests end at the same hour, the order between them does not change the count: once the first one is accepted, the second one starts before its end. The built-in sort is stable in all four languages (equal items stay in the order they came in), so the output is the same everywhere.
sorted and list.sort are Timsort and always stable.Try it
Find the bug
A colleague copied the greedy algorithm and got only three meetings:
def max_meetings(requests): taken = [] free_from = 0 for start, end in sorted(requests, key=lambda r: r[1]): if start > free_from: taken.append((start, end)) free_from = end return takenrequests = [ (8, 16), (12, 15), (9, 12), (15, 18), (11, 13), (17, 20), (14, 16), (18, 20),]taken = max_meetings(requests)for start, end in taken: print(f"{start}–{end}")print(f"Meetings: {len(taken)}")9–1214–1617–20Meetings: 3Which line is the bug on?
Pick the line with the bug.
The 9–12 meeting frees the room at 12, and 12–15 can start exactly then. With the strict > back-to-back meetings are declined. Correct is if start >= free_from:.
The idea
Why by end is right: the exchange argument
Take any best schedule, for example one with 4 meetings. Sort its meetings by time. Greedy first takes the request that ends earliest of all, say 9–12.
- The first meeting of the best schedule ends no earlier than 12, because 12 is the earliest end of all.
- Swap it for 9–12. The other meetings of the schedule start after the end of the old first one, so after 12 too: nothing overlaps, and the count is the same.
- Now both schedules start the same way. Remove 9–12 and the requests that overlap it, and repeat the same for the rest.
Step by step you turn the best schedule into the greedy one without losing a single meeting. So greedy is at least as good as the best: it is the best.
The same argument fails for the other two rules. By start, 8–16 comes first: put it in the place of the first meeting and it shuts the room until 16, and the other meetings no longer fit.
More precisely, if you are curious
Formally the argument is induction on the number of meetings accepted: after k steps there is a best schedule that starts with the first k greedy choices. This is the standard way to prove a greedy algorithm: "the greedy choice is safe" (there is a best solution that contains it) plus "optimal substructure" (the rest is the same task, only smaller). The second property is shared with dynamic programming. The first one is what is missing when greedy fails.
Try it
Fill in the condition
def max_meetings(requests):
taken = []
free_from = 0
for start, end in sorted(requests, key=lambda r: r[1]):
if :
taken.append((start, end))
free_from = end
return takenA request is accepted if it starts no earlier than the moment the room becomes free: start >= free_from.
The idea
A second example: change in euros
The shop's till gives change with as few coins as possible. The euro coins are €2, €1, 50, 20, 10, 5, 2 and 1 cent. Greedy: give the biggest coin that still fits in what is left.
COINS = [200, 100, 50, 20, 10, 5, 2, 1]
def change(cents): given = [] for coin in COINS: while cents >= coin: given.append(coin) cents -= coin return given
def pay(cents): given = change(cents) print(f"{cents} cents: {' '.join(map(str, given))} ({len(given)} coins)")pay(485)485 cents: 200 200 50 20 10 5 (6 coins)For the euro coins this gives the fewest coins for every amount: it is checked against the change table for every amount up to €5. The coins were chosen that way on purpose.
The rule "biggest first" is not right for any coins, though. With coins of 1, 3 and 4 cents, for 6 cents greedy gives 4 + 1 + 1, three coins, and two are enough: 3 + 3. There is no sign you can see at a glance: even with coins each at least twice the next one, greedy can fail. With 1, 4 and 9 cents, for 12 cents it gives 9 + 1 + 1 + 1, and 4 + 4 + 4 is enough. How to look for such cases is in the next lesson.
Try it
Predict the output
COINS = [200, 100, 50, 20, 10, 5, 2, 1]
def change(cents): given = [] for coin in COINS: while cents >= coin: given.append(coin) cents -= coin return given
def pay(cents): given = change(cents) print(f"{cents} cents: {' '.join(map(str, given))} ({len(given)} coins)")
pay(99)The idea
A third example: Kruskal
An internet provider connects neighbourhoods with fibre cable. Every cable laid has a price, and the goal is for all neighbourhoods to be connected for as little money as possible. That is the minimum spanning tree, and Kruskal builds it greedily: it sorts the possible cables by price and takes each next cheapest one, unless it closes a loop (the two neighbourhoods are already connected). Who is connected to whom is kept by union-find.
Here too the argument is an exchange: if the best tree does not contain the cheapest cable between two groups, put it in and remove the more expensive cable from the loop that closes. The price does not go up.
More precisely, if you are curious
Other familiar algorithms are greedy too. Dijkstra always takes the closest vertex not yet processed and never reconsiders it, and that is right because paths have no negative lengths. Huffman coding (behind ZIP and JPEG) always merges the two rarest symbols. What they share is one thing: each has a proof that the choice at the moment is safe.
See it
What it costs
Greedy is a sort, O(n log n), and one pass, O(n). Trying every subset is O(2ⁿ): with 20 requests that is over a million subsets, with 60 it never finishes. Here Bench sorts with merge sort and counts its comparisons. The built-in sort in your language makes a slightly different number, but it grows the same way.
- Every subset
O(2ⁿ) - Greedy by end
O(n log n)
| Algorithm | n = 10 | n = 20 | n = 1,000 | n = 100,000 | n = 1,000,000 |
|---|---|---|---|---|---|
| Every subset | 1,024 | 1,048,576 | ≈ 10³⁰¹ | ≈ 10³⁰¹⁰² | ≈ 10³⁰¹⁰²⁹ |
| Greedy by end | 33 | 85 | 9,691 | 1,636,658 | ≈ 19,639,896 |
def max_meetings(requests): taken = [] free_from = 0 for start, end in sorted(requests, key=lambda r: r[1]): if start >= free_from: taken.append((start, end)) free_from = end return takenExercise
The courier
Solve the task in your editor.
The courier. A courier delivers parcels in a business park. Every customer has said in which window they are at the address: 9–11, 10–12, 11–14, 13–15, 14–17, 16–18 and 17–19. On every pass the courier leaves the parcels of everyone who is at the address right then. How few passes are needed, and at what hours? Write the greedy algorithm and print:
Passes at: 11, 15, 18 (3)Hint: sort the windows by end. The first pass is at the end of the window that ends earliest: later you lose that customer, and earlier you serve no more. Then skip all windows that already contain that hour.
More tasks
- The argument. Write the exchange argument for the courier: why is the first pass at the end of the earliest window no worse than the first pass of the best solution?
- A second room. If the coworking space has two rooms, does "by end" work if you give each request to the room that became free the latest, but in time?
- Prices. If the requests pay different amounts and you want the most money, not the most meetings, greedy by end is no longer right. Find three requests where it is not, and solve the task with the dynamic programming recipe.
Test