Introduction
The activity selection problem asks: given a set of activities, each with a start and finish time, and a single resource (like one lecture hall), what is the maximum number of non-overlapping activities you can schedule? This is a textbook example where a greedy strategy is provably optimal, making it the canonical first proof of the greedy-choice property taught alongside the greedy paradigm.
Cricket analogy: A curator with one pitch must slot as many practice sessions as possible between IPL matches; picking the greedy earliest-ending session first is provably the optimal way to maximize total sessions held.
Algorithm/Syntax
def activity_selection(activities):
"""
activities: list of (start, finish) tuples
returns the maximum set of mutually compatible activities
"""
# Greedy criterion: always pick the activity that finishes earliest
activities = sorted(activities, key=lambda a: a[1])
selected = [activities[0]]
last_finish = activities[0][1]
for start, finish in activities[1:]:
if start >= last_finish:
selected.append((start, finish))
last_finish = finish
return selected
Explanation
The key insight is the greedy criterion: sort by finish time, not by start time or duration, and always pick the earliest-finishing activity that is still compatible with what's already scheduled. Finishing earliest leaves the most room for future activities. The exchange argument proves this: if any optimal solution's first activity finishes later than the greedy choice, you can always swap it for the greedy choice (which frees up at least as much time) without reducing the count of activities selected, so an earliest-finish-time optimal solution always exists.
Cricket analogy: Sorting fielding drills by finish time rather than start time means picking the drill that wraps up soonest, like choosing the shortest net session first, always leaves the most daylight for squeezing in more drills afterward.
Sorting by start time or by shortest duration does NOT guarantee optimality -- only sorting by finish time does. This is a common mistake: a short activity that starts early but finishes late can still block more activities than a slightly longer one that finishes sooner.
Example
activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11), (8, 12), (2, 13), (12, 14)]
result = activity_selection(activities)
print(result)
# Trace: sorted by finish -> (1,4)(3,5)(0,6)(5,7)(3,8)(5,9)(6,10)(8,11)(8,12)(2,13)(12,14)
# Select (1,4) -> last_finish=4
# (3,5): start 3 < 4, skip
# (0,6): start 0 < 4, skip
# (5,7): start 5 >= 4, select -> last_finish=7
# (3,8): start 3 < 7, skip
# (5,9): start 5 < 7, skip
# (6,10): start 6 < 7, skip
# (8,11): start 8 >= 7, select -> last_finish=11
# (8,12): start 8 < 11, skip
# (2,13): start 2 < 11, skip
# (12,14): start 12 >= 11, select -> last_finish=14
# Output: [(1, 4), (5, 7), (8, 11), (12, 14)]
Complexity
Sorting the activities by finish time costs O(n log n); the single linear scan that follows costs O(n). Overall time complexity is O(n log n), with O(n) or O(1) extra space depending on whether the sort is in place and whether you store the selection separately.
Cricket analogy: Sorting a season's fixture list by finish time takes O(n log n), like ranking matches by end date, and then walking through them once to pick non-overlapping fixtures is just an O(n) single pass down the list.
Key Takeaways
- Always sort by finish time, not start time or duration -- this is the correct greedy criterion.
- Greedily pick the earliest-finishing activity compatible with the last selected one.
- The exchange argument guarantees this greedy strategy always finds a maximum-size compatible set.
- Runs in O(n log n) due to sorting, with a single O(n) linear scan afterward.
- A classic entry point for understanding interval scheduling problems in general.
Practice what you learned
1. What is the correct greedy criterion for the activity selection problem?
2. In the activity selection algorithm, when is a new activity added to the selected set?
3. What is the time complexity of the activity selection algorithm?
4. Why does sorting by shortest duration fail to guarantee an optimal solution?
Was this page helpful?
You May Also Like
The Greedy Algorithm Paradigm
Learn how greedy algorithms build solutions one locally optimal choice at a time, and when that strategy actually yields a global optimum.
Fractional Knapsack Problem
Maximize the value of items packed into a capacity-limited knapsack when items can be split, using a greedy value-density strategy.
Recursion vs Iteration
Compare recursive and iterative solutions in terms of clarity, performance, memory usage, and when to prefer each.
Common Algorithm Interview Questions
A curated set of frequently asked algorithm interview questions with clear, technically accurate answers.