Meeting Rooms II
You are given a list of meetings intervals, where intervals[i] = [start, end] means meeting i occupies a room from time start up to, but not including, time end.
A room can host only one meeting at a time. Because a meeting releases its room at its end time, a meeting ending at time t and another starting at time t can use the same room.
Return the smallest number of rooms needed so that every meeting can take place. The meetings are not given in any particular order.
Example 1
Example 2
Example 3
Constraints
1 <= intervals.length <= 1040 <= start < end <= 106
Pattern Path · Intervals & Greedy · problem 116 of 169
Start simple
For every meeting start, count how many meetings are running at that moment and take the maximum: O(n²) time.
The key idea
At any instant the rooms in use must be at least the number of meetings running then, so the answer is at least the maximum overlap. Assigning rooms greedily by start time never needs more than that, so the answer is exactly the maximum overlap.
To measure it, note that only the times matter, not which start pairs with which end. Sort the start times and the end times into two separate lists and sweep with two pointers, like walking along a timeline:
- If the next event is a start that comes before the next end, a new meeting opens: increase the open count.
- Otherwise the earliest-ending meeting has finished, so its room is free: move the end pointer and decrease the count.
When a start and an end share the same time, process the end first; that is how a room is reused by back-to-back meetings. The largest open count seen during the sweep is the answer.
An equivalent method sorts meetings by start and keeps a min-heap of end times: if the earliest end is at or before the new start, reuse that room; the heap's final size is the answer.
Complexity
- Time:
O(n log n) - Space:
O(n)
Python
class Solution:
def minMeetingRooms(self, intervals):
starts = sorted(s for s, _ in intervals)
ends = sorted(e for _, e in intervals)
rooms = best = 0
j = 0 # next meeting end to process
for start in starts:
# Free every room whose meeting has ended by this start (end == start counts as free).
while ends[j] <= start:
rooms -= 1
j += 1
rooms += 1
best = max(best, rooms)
return best
JavaScript
var minMeetingRooms = function(intervals) {
const starts = intervals.map(([s]) => s).sort((a, b) => a - b);
const ends = intervals.map(([, e]) => e).sort((a, b) => a - b);
let rooms = 0, best = 0, j = 0; // j = next meeting end to process
for (const start of starts) {
// Free every room whose meeting has ended by this start (end == start counts as free).
while (ends[j] <= start) {
rooms--;
j++;
}
rooms++;
best = Math.max(best, rooms);
}
return best;
};
What the interviewer is checking
It tests whether you can turn a scheduling question into "maximum overlap" and choose an efficient sweep or heap, including the boundary rule for touching intervals.
Mistakes to avoid
- Treating a meeting that starts exactly when another ends as overlapping (handle ends before starts at equal times).
- Sorting intervals by start and only comparing neighbours, which misses overlaps with earlier, longer meetings.
- Pairing each start with its own end in the two-list sweep; the lists are sorted independently on purpose.
- Forgetting that the input is unsorted.
Follow-ups to expect
- Can you report which room each meeting gets? (Heap of (end, roomId).)
- Can one person attend every meeting? (Sort by start, check neighbours.)
- What if times are small integers? (Difference array plus prefix sums.)
In real software
Calendar room booking, counting concurrent sessions or connections, and sizing a worker pool for overlapping jobs all compute peak overlap this way.