Activity selection
easyFinishing early leaves the most room for what follows. Switch the criterion to earliest start or shortest duration and watch a provably optimal answer become merely a good one.
O(n log n)Space O(1)Saved in this browser - no sign-up, nothing sent anywhere.
How activity selection works
Sort by finish time and sweep: take any activity that starts at or after the last chosen finish. Finishing early leaves the most room for everything after it. Two rules that sound just as reasonable fail on this module's own schedule - earliest start books the long 0-6 activity and manages only two selections, while earliest finish fits three. Shortest duration fails elsewhere, when a brief activity straddles the boundary between two others, like 4-7 between 1-5 and 6-10.
The proof is an exchange argument, and it is worth knowing cold. Take any optimal solution and look at its first activity: it cannot finish earlier than the greedy pick, because the greedy pick has the earliest finish of all. Swap the greedy activity in and the solution stays valid and stays the same size. Repeat the swap down the list and greedy turns out to be optimal - never worse, merely first.
After the sort, one linear pass with a single variable - the last finish time - decides everything. That shape is typical of greedy: the interesting work happens in choosing the sort key, and the loop is trivial. Reach for this pattern whenever intervals compete for one resource and every interval counts equally; the moment intervals carry different weights, greedy breaks and the problem needs dynamic programming.
Step by step
- Eight activities, sorted by finish time: 1-4, 3-5, 0-6, 5-7, 3-9, 5-9, 6-10, 8-11. Nothing is booked yet.
- 1-4 finishes earliest and nothing is booked, so take it. The timeline is now busy until time 4.
- 3-5 starts at 3 and 0-6 starts at 0 - both before 4, so both overlap the booking and are skipped.
- 5-7 starts at 5, at or after the current finish 4. It fits: take it and move the busy marker to 7.
- 3-9, 5-9, and 6-10 all start before 7, so each overlaps the current booking. All three are rejected.
- 8-11 starts at 8, clear of 7. Take it - the third selection, busy until 11.
- Done: 1-4, 5-7, 8-11, three activities. Sorting by start time instead takes 0-6 then 6-10 and manages only two.
Complexity
| Worst case time | O(n log n) |
|---|---|
| Space | O(1) |
The sort dominates; correctness comes from an exchange argument.
Reference implementation
Python
def activity_selection(intervals):
"""Maximum number of non-overlapping intervals."""
intervals.sort(key=lambda x: x[1]) # by finish time - not start!
chosen, last_end = [], float("-inf")
for start, end in intervals:
if start >= last_end:
chosen.append((start, end))
last_end = end
return chosenJavaScript
function activitySelection(intervals) {
intervals.sort((a, b) => a[1] - b[1]); // by finish time
const chosen = [];
let lastEnd = -Infinity;
for (const [s, e] of intervals) {
if (s >= lastEnd) { chosen.push([s, e]); lastEnd = e; }
}
return chosen;
}Worth noticing
Earliest finish, not earliest start
Finishing early leaves the most room for everything after it. Switch the criterion to earliest start and one long activity can block several short ones; shortest-duration fails too, when a brief activity straddles the boundary between two others.
The exchange argument is the proof
Take any optimal solution. Its first activity finishes no earlier than the greedy pick, so swapping the greedy one in keeps it valid and no shorter. Repeat, and the greedy solution is optimal - this is the standard shape of every greedy correctness proof.
O(n log n), and the sort is the whole cost
After sorting, one linear pass decides everything. Whenever a greedy algorithm looks this cheap, the interesting work has already happened in choosing what to sort by.
Common pitfalls
- Sorting by start time. One long early activity hogs the room - on this schedule, taking 0-6 first drops the answer from three activities to two.
- Sorting by duration. A short activity that straddles two others, like 4-7 between 1-5 and 6-10, spends one pick to destroy two.
- Writing start > lastEnd instead of start >= lastEnd, which wrongly rejects back-to-back activities - 6-10 is compatible with an activity ending exactly at 6.
- Carrying the rule to weighted intervals. Once activities have values, earliest finish can happily pick a worthless one; weighted interval scheduling needs dynamic programming.
- Trusting a plausible criterion without a proof. Two of the three rules in this visualizer look right and fail; only earliest finish survives the exchange argument.
Where it is used
- Booking the most meetings into one conference room, the literal textbook framing.
- LeetCode 435, non-overlapping intervals: the minimum removals equal n minus this maximum, same sort and sweep.
- Single-machine job scheduling when every job is worth the same.
- The template for a family of interval problems - merge intervals, minimum arrows to burst balloons, meeting rooms.
Frequently asked questions
What is the time and space complexity of activity selection?
O(n log n) time and O(1) extra space. The sort by finish time dominates the cost entirely; the selection sweep after it is a single linear pass that keeps only one number, the finish time of the last activity taken.
Why does sorting by finish time work?
By exchange: the first activity of any optimal solution finishes no earlier than greedy's pick, so substituting greedy's keeps the solution valid and the same size. Repeating that substitution turns any optimal solution into the greedy one, which means the greedy count was optimal all along.
How do I know if a greedy algorithm is correct?
Prove it, usually with an exchange argument showing any optimal solution can be reshaped into the greedy one without loss. Before proving, hunt for small counterexamples - the start-time and duration rules here both fail on inputs of just three intervals, which is cheaper to find than a proof.
Does greedy still work if activities have weights?
No. When each activity carries a value and the goal is maximum total value, earliest finish can select a low-value activity that blocks a high-value one. Weighted interval scheduling is solved with dynamic programming over intervals sorted by finish time, plus a binary search for the latest compatible activity.