1. One-Liner
Activity Selection sorts activities by finish time and repeatedly picks the next compatible activity that starts after the last chosen one ends—maximizing count.
2. The Problem It Solves
You have activities with [start, finish] times. Only one runs at a time. Find the largest subset with no overlaps (not necessarily maximum weight—that is a harder variant).
3. The Core Idea
Finishing early frees the resource sooner, so more activities can fit afterward. The greedy rule “pick earliest finishing feasible activity” is optimal for the maximum-count objective.
4. How It Works (Step-by-Step)
| Step | What Happens |
|---|---|
| 1. Sort | Sort by finish time ascending |
| 2. Pick first | Select the first activity; set lastFinish |
| 3. Scan | For each next activity, if start ≥ lastFinish, take it and update lastFinish |
| 4. Count / list | Return how many (or which indices) you selected |
5. Dry Run Example
Activities (1,4), (3,5), (0,6), (5,7), (8,9), (5,9) sorted by end: (1,4), (3,5), (0,6), (5,7), (5,9), (8,9). Pick (1,4) → skip overlapping (3,5),(0,6) → pick (5,7) → skip (5,9) → pick (8,9). 3 activities.
6. Key Properties
| Property | Value |
|---|---|
| Greedy choice | Earliest finish first |
| Needs sorting | O(n log n) typically |
| Weights | Max count only (not weighted profit) |
7. Where It Is Used
| Domain | Use |
|---|---|
| Scheduling | Room booking, CPU job batching |
| Competitive programming | Interval greedy templates |
8. Interview Tips
State sort key = end time, prove intuition with exchange argument, and mention weighted interval scheduling needs DP, not this greedy.
9. Comparison with Other Approaches
| Approach | Time | Notes |
|---|---|---|
| This greedy | O(n log n) | Optimal for max count |
| Brute force | Exponential | Try all subsets |
| Weighted max | DP | Different problem |
10. Complexity
| Metric | Value |
|---|---|
| Time | O(n log n) for sort + O(n) scan |
| Space | O(n) for sorted copy, or O(1) extra if sorting in place |
Implementation Example (PYTHON)
def max_activities(start, finish):
idx = sorted(range(len(finish)), key=lambda i: finish[i])
count, last = 0, float('-inf')
for i in idx:
if start[i] >= last:
count += 1
last = finish[i]
return count