You have one meeting room and a set of activities, each with a start and end time. What’s the largest number of non-overlapping activities you can schedule?
The answer: always book the activity that finishes earliest, then repeat. It’s one of the cleanest proofs that a simple greedy rule can be provably optimal — and the foundation for interval scheduling everywhere.
How It Works
- Sort activities by finish time, ascending.
- Select the activity that finishes first.
- Scan the rest in order — keep any activity whose start time is not earlier than the end of the last selected activity.
- Done: the selected set is maximal.
The greedy choice is deliberate: the earliest finisher leaves the most room afterward, so no other activity can block it.
An exchange argument proves optimality: take any optimal solution and swap its first activity for the earliest-finishing one. The swap can’t overlap anything the original could, and the remaining problem is unchanged — so the greedy first pick is safe.
Key Insight
Greedy works here because the constraint is purely about time overlap — once you pick a finisher, the future depends only on the end time, not on which activity it was. That single observation collapses the whole search space. If a later activity started earlier and finished later, it would only ever be worse.
Worked Example
The visualizer uses activities A(1–3), B(2–5), C(4–6), D(6–8), E(5–7):
| Step | Candidate | Starts ≥ last end? | Chosen? |
|---|---|---|---|
| 1 | A (1–3) | — (first) | ✓ A |
| 2 | B (2–5) | 2 < 3 | ✗ |
| 3 | C (4–6) | 4 ≥ 3 | ✓ C |
| 4 | E (5–7) | 5 < 6 | ✗ |
| 5 | D (6–8) | 6 ≥ 6 | ✓ D |
Selected set: A, C, D — 3 activities. Watch the visualizer step through exactly this: each grayed-out candidate fails the start-time check against the current end.
Edge Cases & Pitfalls
- Ties in finish time — any earliest finisher works; pick either.
- Back-to-back intervals — an activity ending at 6 and another starting at 6 are compatible (start ≥ end).
- Overlapping candidates — B and E both conflict with A’s end; the scan simply skips them.
- Sorting matters — without sorting by finish time, the greedy rule breaks. This is a preprocessing requirement, not a choice.
Comparison: Activity Selection vs Other Interval Problems
| Problem | Greedy rule | Optimal? |
|---|---|---|
| Max non-overlapping | Earliest finish | Yes |
| Min rooms (interval partitioning) | Sort by start + heap | Yes |
| Min points to cover intervals | Greedy by end | Yes |
| Weighted interval scheduling | Earliest finish | No → use DP |
Applications
- Meeting room scheduling — booking a single room
- Classroom allocation — packing lectures into one hall
- Resource time-slicing — CPU/job scheduling around deadlines
Practice Trajectory
- Hand-sort the visualizer’s activities by finish time and run the scan yourself.
- Explain why skipping B (2–5) at step 2 can never cost you a solution.
- Construct two activities where picking the earliest start (instead of earliest finish) fails.
- Extend to the min-rooms problem and see why a heap replaces the single pointer.
- Prove the exchange argument for earliest-finish in your own words.