Interval Scheduling and Meeting Rooms Problem
- Max non-overlapping: sort by END time (not start time — this is the common mistake), pick greedily. Sorting by start time gives a suboptimal result.
- Min meeting rooms: sort by start time, use a min-heap of end times. Size of heap at any point = rooms in use. Peak heap size = answer.
- Merge intervals: sort by start time, linear scan — merge if next start <= current end. O(n log n) for sort, O(n) for merge.
Interval scheduling appears in every operating system (process time slots), every calendar application (meeting conflict detection), and virtually every resource allocation problem. The three variants — maximise non-overlapping intervals, minimise rooms needed, merge overlapping intervals — are among the most frequently asked algorithmic interview problems at top companies.
All three have elegant O(n log n) greedy solutions, but the correctness argument for each is different. Maximum non-overlapping uses earliest deadline first with an exchange argument. Minimum rooms uses a priority queue sweep. Merge intervals is just careful iteration. Knowing all three and why each works — not just what to code — is what distinguishes thorough preparation.
Problem 1 — Maximum Non-Overlapping Intervals
Greedy insight: always pick the interval that finishes earliest. This leaves maximum room for future intervals.
def max_non_overlapping(intervals: list[tuple]) -> list[tuple]: """ Returns maximum set of non-overlapping intervals. Greedy: sort by end time, always pick earliest finish. """ intervals = sorted(intervals, key=lambda x: x[1]) selected = [] last_end = float('-inf') for start, end in intervals: if start >= last_end: # no overlap selected.append((start, end)) last_end = end return selected intervals = [(1,4),(3,5),(0,6),(5,7),(3,9),(5,9),(6,10),(8,11),(8,12),(2,14),(12,16)] result = max_non_overlapping(intervals) print(f'Max non-overlapping: {len(result)} → {result}')
Problem 2 — Minimum Meeting Rooms
Use a min-heap tracking end times of active meetings. For each meeting start, if the earliest-ending active meeting has ended, reuse its room.
import heapq def min_meeting_rooms(intervals: list[tuple]) -> int: if not intervals: return 0 intervals = sorted(intervals, key=lambda x: x[0]) heap = [] # end times of active meetings for start, end in intervals: if heap and heap[0] <= start: heapq.heapreplace(heap, end) # reuse room else: heapq.heappush(heap, end) # new room needed return len(heap) print(min_meeting_rooms([(0,30),(5,10),(15,20)])) # 2 print(min_meeting_rooms([(7,10),(2,4)])) # 1
1
Problem 3 — Merge Overlapping Intervals
Sort by start time, merge consecutive overlapping intervals.
def merge_intervals(intervals: list[tuple]) -> list[tuple]: if not intervals: return [] intervals = sorted(intervals, key=lambda x: x[0]) merged = [intervals[0]] for start, end in intervals[1:]: if start <= merged[-1][1]: # overlapping merged[-1] = (merged[-1][0], max(merged[-1][1], end)) else: merged.append((start, end)) return merged print(merge_intervals([(1,3),(2,6),(8,10),(15,18)])) # [(1,6),(8,10),(15,18)] print(merge_intervals([(1,4),(4,5)])) # [(1,5)]
[(1, 5)]
Why Earliest Finish Time is Optimal
Claim: picking the interval with the earliest finish time is always in some optimal solution. Proof: suppose optimal starts with interval A instead of E (earliest finish). Replace A with E — since E finishes earlier, this can only improve future compatibility. By induction, greedy is optimal.
🎯 Key Takeaways
- Max non-overlapping: sort by END time (not start time — this is the common mistake), pick greedily. Sorting by start time gives a suboptimal result.
- Min meeting rooms: sort by start time, use a min-heap of end times. Size of heap at any point = rooms in use. Peak heap size = answer.
- Merge intervals: sort by start time, linear scan — merge if next start <= current end. O(n log n) for sort, O(n) for merge.
- Why earliest deadline works: if you could improve by not taking the earliest-finishing interval first, you could swap it in — but swapping never makes things worse. Exchange argument.
- LeetCode connection: 435 (non-overlapping), 252/253 (meeting rooms), 56 (merge intervals). These four problems cover 80% of interval scheduling interview questions.
Interview Questions on This Topic
- QWhy does sorting by end time give the optimal solution for interval scheduling?
- QHow does the min-heap approach solve the minimum meeting rooms problem?
- QWhat is the difference between interval scheduling maximisation and minimum room allocation?
- QHow would you find the minimum number of intervals to remove to make the rest non-overlapping?
Frequently Asked Questions
Is sorting by start time or end time correct for max non-overlapping?
End time. Sorting by start time is a common mistake — it doesn't give optimal results. Example: [(0,100),(1,2),(3,4)] — earliest start is (0,100) which blocks everything; earliest finish (1,2) is much better.
Developer and founder of TheCodeForge. I built this site because I was tired of tutorials that explain what to type without explaining why it works. Every article here is written to make concepts actually click.