Activity selection
In one line
To fit the most non-overlapping activities, sort by end time and keep every activity that starts after the last one you kept ends.
What it is
Activity selection asks: given activities with start and end times and one resource (a room, a machine, a person), what is the largest set of activities that do not overlap?
The greedy answer is to always keep the activity that finishes earliest among those that still fit. Finishing early leaves the most time for everything after it.
The same idea solves several interview problems in disguise: the fewest intervals to remove so the rest do not overlap (n minus the maximum kept), and the fewest arrows to burst balloons (each arrow is placed at the end of a kept interval).
Why interviewers ask
It is the textbook example of a provably correct greedy, so interviewers use it to test whether you choose the right sort key and can justify it. Many candidates sort by start time or by duration, which fails; explaining why earliest end is safe shows real understanding.
How it works
- 1Sort activities by end time (ties in any order).
- 2Keep a variable last_end, starting at minus infinity.
- 3Scan in order. If an activity starts at or after last_end (for half-open intervals [start, end)), keep it and set last_end to its end. Otherwise skip it.
- 4The number kept is the maximum. The number skipped is the minimum to remove.
- 5Why it is correct: let the greedy pick be g, the earliest-ending activity. Any optimal schedule has some first activity o that ends no earlier than g. Replace o with g: g ends no later, so it does not clash with anything after o. The schedule stays the same size, so some optimal schedule starts with g.
Worked example · Six talks, one room
- Talks as [start, end): (1,3), (2,5), (4,6), (6,8), (5,9), (8,10). Sorted by end they are already in this order.
- last_end = -inf. (1,3): 1 >= -inf, keep. last_end = 3. Kept: 1.
- (2,5): 2 < 3, overlaps, skip.
- (4,6): 4 >= 3, keep. last_end = 6. Kept: 2.
- (6,8): 6 >= 6, touching is fine for half-open intervals, keep. last_end = 8. Kept: 3.
- (5,9): 5 < 8, skip. (8,10): 8 >= 8, keep. last_end = 10. Kept: 4.
- Answer 4 talks; the minimum number to cancel is 6 - 4 = 2. Sorting by start time would also pick (1,3) first here, but on input (1,10), (2,3), (4,5) it keeps 1 talk instead of 2.
Picture it
If you want to watch as many films as possible at a festival with one screen, always pick the film that lets you out of the cinema soonest. A long film that starts early looks attractive but eats the evening; ending early keeps every later option open.
Reference code
def max_non_overlapping(intervals):
"""Maximum number of intervals with no overlap.
Intervals are [start, end); touching ends are allowed."""
count = 0
last_end = float("-inf")
for start, end in sorted(intervals, key=lambda iv: iv[1]):
if start >= last_end: # compatible with the last pick
count += 1
last_end = end # earliest finish so far
return count
def erase_overlap_intervals(intervals):
"""Fewest intervals to remove so the rest do not overlap."""
return len(intervals) - max_non_overlapping(intervals)
# max_non_overlapping([(1,3),(2,5),(4,6),(6,8),(5,9),(8,10)]) -> 4
Sort by end time, then one pass keeps every interval that starts at or after the last kept end. O(n log n) time, O(1) extra space beyond sorting. Change >= to > if touching closed intervals count as overlapping.
Key patterns
Maximum non-overlapping intervals
When: Keep as many intervals as possible
How: Sort by end, keep if start >= last_end.
Minimum removals (non-overlapping intervals)
When: Remove the fewest intervals so none overlap
How: Answer is n minus the maximum kept.
Minimum arrows / points to stab intervals
When: Choose the fewest points so every interval contains one
How: Sort by end; shoot at the end of the first interval, skip all intervals that contain it, repeat. Watch whether touching counts as overlapping (closed intervals use start > last_end).
Weighted version
When: Intervals have values and you maximise total value
How: Greedy fails; sort by end and use DP where dp[i] = max(dp[i-1], value[i] + dp[last compatible]) with binary search.
Real-world use
Meeting room and venue booking
Booking tools that try to fit as many requests as possible into one room or one court use earliest-finish-first as the baseline rule before adding priorities.
Ad and broadcast slots
Placing the maximum number of fixed-time spots into one channel's schedule with no overlap is the same problem; weighted versions (spots with different revenue) need DP instead.
Job scheduling on a single machine
Batch systems that must run as many fixed-window jobs as possible on one exclusive resource, such as a lab instrument or a GPU slot, use this rule.
Removing conflicts in calendars
Finding the fewest events to drop so a personal calendar has no double bookings is n minus the activity selection answer.
In a project
A coworking space wants a tool that, given tomorrow's booking requests for a single podcast studio, accepts as many as possible and tells the rest to pick another time.
- Store each request as a half-open interval [start, end) in minutes since midnight so back-to-back bookings are allowed.
- Sort requests by end time and run the greedy sweep, keeping last_end.
- Return accepted requests and, for each rejected one, the nearest free gap from the accepted schedule.
- If some customers pay more, note that maximising revenue is weighted interval scheduling and use DP with binary search instead of this greedy.
Impact: The studio fits the maximum possible number of sessions each day in O(n log n) time, and rejected customers get an immediate alternative instead of a manual back-and-forth.
Trade-offs
Use it when
- One resource, all activities equally valuable, maximise the count
- Minimum removals or minimum stabbing points on intervals
- Input is large and you need O(n log n)
Avoid it when
- Activities have different weights or profits: use weighted interval scheduling (DP)
- There are several identical resources and every activity must be placed: that is a meeting rooms / sweep line problem
- Activities have deadlines and durations rather than fixed times: a different greedy (by deadline) or a heap applies
Cost: O(n log n) time for sorting plus O(n) for the sweep; O(1) extra space.
Common mistakes
- Sorting by start time: one long early interval can block many short ones.
- Sorting by duration: a short interval can still overlap two others that would both fit.
- Getting the boundary wrong: decide whether [1,3] and [3,5] overlap and use >= or > accordingly.
- Applying the unweighted greedy to a weighted problem.
- Confusing this with meeting rooms, which asks how many rooms are needed for all meetings.
Interview questions
Quick revision
- Sort by END time, keep if start >= last_end.
- Max kept = answer; n - max kept = minimum removals.
- Arrows / stabbing points: shoot at each kept interval's end.
- Check the boundary rule: half-open allows touching.
- Counterexample for start-time sort: (1,10), (2,3), (4,5).
- Weighted version is DP, not greedy.
- O(n log n) time, O(1) extra space.
Check yourself
1. Which sort key makes the activity selection greedy correct?
2. Intervals [1,2), [2,3), [3,4), [1,3). What is the minimum number to remove so none overlap?
3. Each activity now has a different profit and you maximise total profit. What should you use?
4. Intervals (1,10), (2,3), (4,5). How many does a start-time greedy keep, versus the optimum?
Related
Saved on this device. Create a free account to keep it on every device.
Practise this with Sam
A real mock interview, out loud, with an honest scorecard. Free to start.