How Do You Solve the Meeting Rooms Problem?
Learn to solve the meeting rooms problem with two sorted arrays or a min-heap, and how to explain it in a coding interview.
Expected Interview Answer
The meeting rooms problem asks for the minimum number of rooms needed to host a set of meetings, and it is solved by separating start and end times into two sorted arrays, then sweeping through: every time a meeting starts before the earliest currently-running meeting ends, you need one more room, tracked with a running counter and its maximum.
Sort start times and end times independently in O(n log n). Use two pointers, one over starts and one over ends. Advance through starts in order; each time the current start is less than the current earliest end, increment the active-room counter (a new room is needed) without moving the end pointer; otherwise, a room has freed up, so decrement the counter and advance the end pointer, then still process the current start by incrementing again. Track the maximum value the counter ever reaches — that is the answer. An equivalent, often cleaner, approach uses a min-heap of end times: push each meeting's end time when it starts, and whenever the heap's smallest end time is less than or equal to the new meeting's start, pop it (reusing that room) before pushing the new end time; the heap's peak size is the answer.
- O(n log n) via sorted start/end arrays or a min-heap
- Directly answers "minimum rooms" without simulating a full calendar
- Two clean implementations: two-pointer sweep or min-heap
- Generalizes to any "minimum concurrent resources" problem
AI Mentor Explanation
A cricket academy wants to know the fewest practice nets needed to run every scheduled coaching session without any team waiting. They list every session's start time and separately every session's end time, both sorted, then sweep through the starts: whenever a new session begins before the earliest currently-running session ends, another net must be opened, since no net is free yet. Whenever a session ends before or exactly when the next one starts, that net becomes free and can be reused, so the net count drops. The maximum number of simultaneously open nets across the whole sweep is the minimum nets required.
Step-by-Step Explanation
Step 1
Split into start and end arrays
Extract all start times and all end times into two separate arrays and sort each in O(n log n).
Step 2
Two-pointer sweep
Advance through starts; if current start < current earliest end, a new room is needed (increment counter).
Step 3
Free rooms as meetings end
If current start >= current earliest end, a room frees up (advance end pointer, decrement counter) before processing the start.
Step 4
Track the peak counter
The maximum value the active-room counter ever reaches during the sweep is the minimum rooms needed.
What Interviewer Expects
- Recognize this as a "max overlap count" problem, not simple interval merging
- Give the two-pointer sorted-arrays solution and/or the min-heap alternative
- State O(n log n) time, O(n) space
- Correctly handle the boundary: a meeting ending exactly when another starts frees the room
Common Mistakes
- Confusing this with interval scheduling maximization (a different problem entirely)
- Using strict < vs <= incorrectly at the boundary, off-by-one in room count
- Forgetting to track the maximum concurrent count, only the final count
- Sorting starts and ends together instead of as two independent arrays
Best Answer (HR Friendly)
“I split all the meetings into separate sorted lists of start times and end times, then sweep through: every time a meeting starts before the earliest running one has ended, I need one more room, and every time one ends in time, a room frees up for reuse. The highest number of rooms in use at any point during that sweep is the answer, and I can also solve it with a min-heap of end times if that is preferred.”
Code Example
def min_meeting_rooms(intervals):
starts = sorted(iv[0] for iv in intervals)
ends = sorted(iv[1] for iv in intervals)
rooms = 0
max_rooms = 0
s = e = 0
while s < len(starts):
if starts[s] < ends[e]:
rooms += 1
s += 1
else:
rooms -= 1
e += 1
max_rooms = max(max_rooms, rooms)
return max_rooms
print(min_meeting_rooms([(0, 30), (5, 10), (15, 20)])) # 2Follow-up Questions
- How would you solve this with a min-heap instead of two sorted arrays?
- How would you also report which room each meeting was assigned to?
- How would this change if meetings could be rescheduled to minimize rooms further?
- What is the difference between this problem and simply checking if any two meetings overlap?
MCQ Practice
1. What do you sort separately in the meeting rooms two-pointer solution?
Splitting into independently sorted start and end arrays enables the two-pointer overlap sweep.
2. In the min-heap approach, what triggers popping the heap?
If the earliest-ending meeting already finished by the time the new one starts, its room can be reused.
3. What does the final answer represent in the meeting rooms problem?
The minimum rooms needed equals the peak number of meetings happening simultaneously.
Flash Cards
What two arrays does the two-pointer meeting rooms solution use? — Sorted start times and sorted end times.
What increments the room counter? — A start time occurring before the current earliest end time.
What is the min-heap alternative approach? — Push end times as meetings start; pop when the smallest end time <= new start time; track peak heap size.
What is the time complexity of the meeting rooms problem? — O(n log n), from sorting or heap operations.