Interval Problems: Meeting Rooms I and II
Interval questions come up constantly because they test sorting, greedy reasoning and heaps all at once.
Meeting Rooms I (can one person attend all meetings?)
Sort by start time and check whether any meeting starts before the previous one ends.
def can_attend(intervals):
intervals.sort()
return all(intervals[i][0] >= intervals[i-1][1]
for i in range(1, len(intervals)))
Meeting Rooms II (minimum number of rooms)
Sort by start; keep a min-heap of end times for rooms in use. If the earliest-ending room is free when the next meeting starts, reuse it.
import heapq
def min_rooms(intervals):
intervals.sort()
ends = []
for s, e in intervals:
if ends and ends[0] <= s:
heapq.heapreplace(ends, e)
else:
heapq.heappush(ends, e)
return len(ends)
O(n log n) time. An equally good alternative is a sweep line: sort all starts and all ends separately, walk both with two pointers, and track the maximum number of meetings open at once.
Clarify the boundary
Does a meeting ending at 10:00 conflict with one starting at 10:00? Usually no, hence <= above, but ask the interviewer. It's an easy way to show care.
Related problems
- Merge Intervals (56): sort, then extend or append.
- Non-overlapping Intervals (435): greedy by end time, counting removals.
- Insert Interval (57) and Employee Free Time (759).
Disclosure: I'm on the team behind Linkjob AI, a coding interview assistant.