Schedule the Most Meetings by Earliest Finish

Activity selection asks for the largest number of meetings that can share one room without overlapping, and the greedy rule that solves it is to keep whichever meeting finishes first. This card walks the rule through six meetings and gives its cost.

The meetings are A (1 to 3), B (2 to 5), C (4 to 7), D (6 to 8), E (5 to 9) and F (8 to 10), in hours. A meeting may start at the moment another ends. The rule sorts them by end time, then scans once: keep a meeting if it starts no earlier than the end of the last meeting kept, and skip it otherwise.

A run of the rule printed one row per meeting in the order the scan meets them, which is the order of their end times.

Each row compares one start with one number, the end of the last meeting kept, which is 3 while B is checked, 7 while D, E and F are checked, and 10 once F is in.

The earliest finish is the right measure because it leaves the most room. Whatever meeting a best schedule starts with, the meeting that ends first ends no later, so swapping it in cannot make anything after it overlap. Proving a Greedy Choice With an Exchange Argument turns that sentence into a proof. Sorting by start time looks just as natural and fails: a meeting from 0 to 9 starts first and blocks everything.

The sort costs O(n log n) and the scan O(n), so the whole algorithm is O(n log n), and O(n) if the meetings arrive already sorted by end time. It needs no memory beyond the sorted list and the one end time it remembers.