What is the Activity Selection Problem?
Learn the classic activity selection problem, why sorting by finish time is optimal, and how to explain the greedy proof.
Expected Interview Answer
The activity selection problem is the classic greedy exercise of choosing the maximum number of non-conflicting activities from a set given each activity's start and finish time, solved by sorting activities by finish time and greedily selecting each activity whose start time is not earlier than the finish time of the last selected activity.
It is essentially the same underlying algorithm as interval scheduling maximization, framed as the textbook introduction to greedy algorithm design and proof by exchange argument or induction. Sort all activities by finish time in O(n log n), select the first activity, then scan the rest in order, selecting any activity whose start time is greater than or equal to the finish time of the most recently selected activity. This greedy choice is optimal because always freeing up the earliest possible time leaves maximum room for subsequent activities, which can be proven rigorously by showing any optimal solution can be transformed to include the earliest-finishing activity without reducing the count. It is frequently the first greedy-algorithm problem taught because the correctness proof itself demonstrates the greedy-choice property and optimal substructure.
- O(n log n) via sorting by finish time, O(n) for the scan
- Classic teaching example of the greedy-choice property
- Optimal substructure makes the proof of correctness clean
- Directly reusable for real scheduling and resource-allocation problems
AI Mentor Explanation
A coach must pick the maximum number of non-clashing net sessions from a long list of requested time slots for a single net. The coach sorts every request by its finish time, always accepting the request that frees the net earliest among those not conflicting with an already-accepted session. This is the textbook proof that greedy works here: accepting the earliest-finishing session first can never be worse than any other choice, because it always leaves at least as much room for the remaining requests. Walking the sorted list once and picking every non-conflicting request in order gives the provably maximum number of sessions.
Step-by-Step Explanation
Step 1
Sort activities by finish time
Sort the whole list ascending by finish time in O(n log n) — the greedy key.
Step 2
Select the first activity
Always accept the activity with the earliest finish time first.
Step 3
Scan and apply the greedy rule
For each remaining activity, accept it if its start >= the finish time of the last accepted activity.
Step 4
Prove optimality by exchange argument
Show any optimal solution can be modified to include the earliest-finishing activity without losing count, establishing the greedy-choice property.
What Interviewer Expects
- Sort by finish time, not start time or duration
- Walk through the exchange-argument proof of why greedy is optimal here
- State O(n log n) time complexity
- Recognize this is the same core idea as interval scheduling maximization
Common Mistakes
- Sorting by duration or start time instead of finish time
- Assuming greedy always works without being able to justify why for this specific problem
- Confusing activity selection (unweighted, maximize count) with weighted interval scheduling (needs DP)
- Forgetting to update the "last selected finish time" reference after each acceptance
Best Answer (HR Friendly)
“This is the classic textbook greedy problem: given a bunch of activities each with a start and finish time competing for one resource, I sort them by when they finish and greedily take whichever finishes soonest without conflicting with what I already picked. It is the go-to example for explaining why greedy algorithms work, because the proof that this choice is optimal is short and clean.”
Code Example
def activity_selection(activities):
# activities: list of (start, finish)
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
acts = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
print(activity_selection(acts))Follow-up Questions
- How would you prove the greedy choice is optimal using an exchange argument?
- How would this differ if each activity had an associated profit or weight?
- How would you extend activity selection to two or more identical resources?
- What is the relationship between activity selection and the interval scheduling maximization problem?
MCQ Practice
1. What is the greedy sort key for the activity selection problem?
Sorting by finish time and greedily selecting earliest-finishing non-conflicting activities is optimal.
2. Which property does activity selection demonstrate for greedy algorithm design?
It is the canonical textbook example proving a locally optimal (greedy) choice leads to a globally optimal solution.
3. What is the time complexity of the activity selection algorithm?
The sort by finish time dominates at O(n log n); the selection scan is O(n).
Flash Cards
What is the greedy key in activity selection? — Finish time, ascending.
What algorithmic property does this problem classically teach? — The greedy-choice property combined with optimal substructure.
What is the time complexity of activity selection? — O(n log n), from sorting by finish time.
How does activity selection differ from weighted interval scheduling? — Activity selection maximizes count via greedy; weighted interval scheduling maximizes total weight and needs dynamic programming.