Activity Selection Problem
You'll learn how to select the maximum number of non-overlapping activities by always choosing the one that finishes earliest.
The Core Idea
Imagine you're organizing your day and have a list of activities, each with a start and end time. You want to do as many activities as possible, but they can't overlap. How do you choose?
The Activity Selection Problem solves this by using a greedy strategy: always pick the activity that finishes first among the remaining choices. This leaves the most room for future activities.
Why "Finish First" Works
Think of it like booking a conference room. If you always choose the meeting that ends earliest, you free up the room sooner for other meetings. A meeting that runs late blocks more future possibilities.
The algorithm:
- Sort all activities by their finish time
- Select the first activity (finishes earliest)
- For each remaining activity, if its start time is after or equal to the last selected activity's finish time, select it
- Repeat until no activities remain
Example Walkthrough
Activities: [(1,3), (2,5), (4,7), (1,8), (5,9), (8,10)] (start, finish pairs)
After sorting by finish time: [(1,3), (2,5), (4,7), (1,8), (5,9), (8,10)]
- Select (1,3) — finishes at 3
- Skip (2,5) — starts at 2, overlaps
- Skip (4,7) — starts at 4, overlaps
- Skip (1,8) — starts at 1, overlaps
- Select (5,9) — starts at 5 ≥ 3, no overlap
- Select (8,10) — starts at 8 ≥ 9? No, but starts at 8, overlaps with 9... Wait: starts at 8, last finished at 9, so skip
Maximum activities: 2 or 3 depending on ties.
Key Takeaway: The Activity Selection Problem demonstrates greedy algorithms at their best—by always choosing the activity that finishes earliest, you maximize opportunities for future selections and guarantee an optimal solution.