~/home/finish first, fit the most: interval scheduling
Algorithm · Greedy
Finish First, Fit the Most.
Don't memorize activity selection — watch the greedy choice pay off. You have intervals fighting for one resource — one meeting room, one CPU — and you want to fit the most that don't overlap. The rule is almost too simple: sort by earliest finish time, then take each interval that starts after the last one you took ends. Finishing soonest leaves the most room for everything else, which is exactly why this beats sorting by shortest or by earliest start.
one resource · sort by finish · take if start ≥ last finish · provably optimal
ACTIVITY SELECTION
Pick the most non-overlapping intervals that can share a single resource.
SORT BY FINISH
Order the intervals by earliest end time — the whole trick lives here.
TAKE IF FREE
Take an interval only if its start is ≥ the finish of the last one you took.
WHY IT WORKS
Ending soonest frees the resource earliest, leaving maximum room for the rest.
schedule.sim — 6 intervals, one room
Ready
Six intervals, already sorted by finish time (top = earliest end). Take the first, then scan down: keep any whose start is at or after the last finish, skip the rest. Press Step.
take interval if start ≥ lastEnd; then lastEnd = its end
0
Chosen
—
Last finish
The earliest finish is always safe
Greedy algorithms usually need a proof that the locally best move does not doom you later. Here the move is: among all intervals, commit to the one that finishes first. The argument is an exchange. Take any optimal schedule and look at its first interval by finish time. If it is not the globally earliest-finishing interval, swap it out for that one — the replacement ends no later, so it cannot overlap anything the optimal schedule kept afterward, and the count is unchanged. So there is always an optimal schedule that starts with the earliest-finishing interval. Remove it and everything it overlaps, and the same argument applies to what remains. That is why the simple scan — sort by finish, take when the start clears the last finish — produces a maximum set every time. Sorting by shortest length or earliest start has no such guarantee.
01
Sort by finish time
Order all intervals by their end time, earliest first. This is the O(n log n) step.
02
Track the last finish
Keep lastEnd, the finish of the most recently chosen interval, starting at −∞.
03
Take or skip
Scan in order: if start ≥ lastEnd, take it and set lastEnd to its end; otherwise skip — it overlaps.
04
Optimal by exchange
The earliest finisher is always safe to include, so the greedy set is a maximum set.
Time
O(n log n)
Space
O(1)
Criterion
Earliest finish
Result
Max count
This is the textbook example of a greedy that is provably optimal, alongside Huffman coding, Kruskal and Dijkstra. It solves single-resource scheduling everywhere: booking one meeting room, sequencing jobs on one machine, assigning a taxi to non-overlapping rides. Change the goal to maximum total weight instead of maximum count, though, and greedy breaks — weighted interval scheduling needs dynamic programming (sort by finish, then for each interval take it plus the best compatible earlier solution, located with a binary search).
Check yourself
1 · To maximize non-overlapping intervals, sort by…
Finishing soonest frees the resource earliest, leaving the most room. It is the only criterion that is provably optimal for maximizing the count.
2 · When do you take the next interval?
If the start clears the last finish, there is no overlap, so take it and advance lastEnd. Otherwise it conflicts and is skipped.
3 · Why is sorting by shortest interval wrong?
One tiny interval sitting across the boundary of two longer ones can knock both out, losing a better pair. Earliest-finish avoids this trap.
Questions
Why not just pick the shortest intervals?
Because a single short interval can overlap two longer ones that do not overlap each other, blocking both and costing you a selection. Earliest-finish-first has a clean exchange-argument proof of optimality; shortest-first and earliest-start-first do not.
What if intervals have weights or values?
Then you want maximum total weight, not maximum count, and greedy fails. Weighted interval scheduling is a dynamic-programming problem: sort by finish, and for each interval choose the better of skipping it or taking it plus the best solution that ends before it starts (found with binary search).
Where does this show up in practice?
Anywhere one resource is shared over time: reserving a single meeting room, scheduling jobs on one machine, matching one vehicle to non-overlapping trips. It is also a warm-up for interval problems like merging intervals and finding the minimum number of rooms.
Sort by finish, and greed is optimal.
Take the interval that ends soonest, skip whatever it overlaps, repeat — and you have fit the maximum number into one resource.