Practice: Meeting Rooms
Greedy that works.
You have one meeting room, and lots of meeting requests, each with a start and an end time. Fit in as many meetings as possible. Pause. Which meeting should you pick first?

- One room
- Lots of requests
- Fit in as many as possible
Earliest finish first
The greedy trick is to always pick the meeting that finishes earliest. That leaves the most time for everything else. We sort by end time, then take each meeting that starts after the last chosen one ends. Run it. Three meetings fit, and it can be proven that no plan fits more.
def most_meetings(meetings):
chosen, last_end = [], 0
for start, end in sorted(meetings, key=lambda m: m[1]):
if start >= last_end:
chosen.append((start, end))
last_end = end
return chosen
requests = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14)]
print(most_meetings(requests))[(1, 4), (5, 7), (8, 11)]
Trusting a greedy choice
A greedy algorithm is correct only if the greedy choice can never hurt you later. Picking the earliest finish never blocks a better plan, so it's safe. For coins with strange values, the biggest coin can block a better plan, so it isn't. When in doubt, try to find a counter example, like we did with the coins.
| key | value |
|---|---|
| Earliest finish | provably optimal |
| Biggest coin | fails for odd coins |
| Test it | look for a counter example |
| Cost | usually a sort, O(n log n) |
Summary
Picking the meeting that ends earliest fits the most meetings, and it's provably optimal. Next, dynamic programming, for when greedy isn't enough.
Key takeaways- Sort by end time
- Take if it fits
- Greedy, and correct