Quiz
Warm-up from lesson 3-3: the sort-then-solve pattern. Why did sorting meetings make the overlap check easy?
The greedy leap
A greedy algorithm builds a solution by repeatedly taking the choice that looks best right now, and never undoing it. No recursion tree, no backtracking, usually just sort + one pass.
The classic: maximum meetings. Given meetings with start and end times, one room, how many can you host?
The greedy rule that works: always take the meeting that ends earliest (among those that fit). Why? Whatever meeting you take, what matters for the future is only when the room frees up. The earliest-ending compatible meeting frees the room soonest, leaving maximal space for the rest.
That style of justification has a name: the exchange argument. Take any optimal schedule, swap its first meeting for the earliest-ending one, and it stays valid and just as large. So the greedy choice is never wrong.
Code exercise · python
Run this. Sort by end time, then one pass: take a meeting whenever its start is at or after the time the room frees up.
Quiz
Why sort by END time instead of start time or duration?
Code exercise · python
Your turn. US cashiers make change greedily: always hand over the biggest coin that fits. Write make_change(cents) using coins 25, 10, 5, 1, returning the list of coins used. For US coins, greedy happens to be optimal.