What is the Interval Scheduling Problem?
Learn the interval scheduling problem, why sorting by end time is optimal, and how to answer this greedy algorithms interview question.
Expected Interview Answer
The interval scheduling problem asks for the maximum number of non-overlapping intervals you can select from a set, and it is solved optimally with a greedy strategy: sort intervals by end time and repeatedly pick the interval that finishes earliest among those that do not conflict with what you already chose.
The key insight is that choosing the interval with the earliest finish time always leaves the most room for future choices, so a greedy approach — not dynamic programming — gives the provably optimal answer. Sort all intervals by their end time in O(n log n), then walk through them once, keeping a running 'last end time' and accepting any interval whose start is greater than or equal to it. This runs in O(n log n) total, dominated by the sort. The same greedy-by-finish-time idea underlies classroom scheduling, CPU job selection, and any 'pick the most non-conflicting items' interview question.
- O(n log n) time via a single sort plus one linear pass
- Provably optimal, not just a heuristic
- No extra data structure beyond the sorted list needed
- Pattern reused across many scheduling-style problems
AI Mentor Explanation
A stadium's single practice net can only host one team drill at a time, and dozens of teams submit requested time slots that overlap. The groundskeeper always accepts whichever pending request finishes soonest among the ones that do not clash with an already-booked slot, then moves on to the next earliest-finishing request. This greedy finish-first rule is provably the way to pack the most drills into one net, because grabbing the slot that frees up fastest always leaves the most room afterward. Sorting all requests by end time once, then scanning left to right, is exactly this process.
Step-by-Step Explanation
Step 1
Sort by end time
Sort all intervals by their finish time in O(n log n); this ordering is the entire trick.
Step 2
Track the last accepted end
Initialize lastEnd to negative infinity before scanning.
Step 3
Scan and greedily accept
For each interval in sorted order, accept it if its start is >= lastEnd, then update lastEnd to its finish.
Step 4
Count accepted intervals
The count of accepted intervals is the maximum possible non-overlapping set.
What Interviewer Expects
- Sort by end time, not start time
- Explain why greedy-by-earliest-finish is provably optimal (exchange argument)
- State O(n log n) overall complexity
- Distinguish this from interval merging or scheduling with weights (which needs DP)
Common Mistakes
- Sorting by start time instead of end time
- Trying to solve with dynamic programming when greedy already gives the optimal answer
- Forgetting to update lastEnd only when an interval is accepted
- Confusing this with weighted interval scheduling, which does require DP
Best Answer (HR Friendly)
“When I need to fit as many non-overlapping bookings as possible into one resource, I sort everything by when it ends and greedily grab whichever finishes soonest without clashing with what I already picked. It sounds almost too simple, but it is mathematically the optimal strategy, and it runs in O(n log n).”
Code Example
def max_non_overlapping(intervals):
intervals = sorted(intervals, key=lambda iv: iv[1])
count = 0
last_end = float("-inf")
for start, end in intervals:
if start >= last_end:
count += 1
last_end = end
return count
# example
jobs = [(1, 3), (2, 5), (4, 6), (6, 8), (5, 9)]
print(max_non_overlapping(jobs)) # 3Follow-up Questions
- How would this change if each interval had a weight and you wanted maximum total weight?
- How would you also return which intervals were selected, not just the count?
- Why does sorting by start time not give the optimal answer?
- How would you handle intervals that touch exactly at the boundary (end equals next start)?
MCQ Practice
1. What is the correct greedy key for the interval scheduling maximization problem?
Sorting by end time and greedily picking the earliest-finishing non-conflicting interval is provably optimal.
2. What is the time complexity of the greedy interval scheduling algorithm?
Sorting dominates at O(n log n); the scan afterward is O(n).
3. Why is greedy-by-earliest-finish optimal for this problem?
An exchange argument shows swapping any optimal solution to use the earliest-finishing interval never makes it worse, and it maximizes remaining room.
Flash Cards
What do you sort by in interval scheduling maximization? — End (finish) time, ascending.
Is interval scheduling solved with greedy or DP? — Greedy — sorting by end time gives the provably optimal answer.
What is the time complexity of interval scheduling? — O(n log n), dominated by the sort.
What condition accepts a new interval in the scan? — Its start time is >= the end time of the last accepted interval.