Meeting Rooms II
Problem
Given an array of meeting time intervals [[start1,end1],[start2,end2],...], find the minimum number of conference rooms required to hold all the meetings — i.e., the maximum number of meetings happening concurrently at any point in time.
Examples
Example 1
Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2
Explanation: [0,30] overlaps both [5,10] and [15,20], but those two don't overlap each other — max 2 concurrent.
Example 2
Input: intervals = [[7,10],[2,4]]
Output: 1
Explanation: No overlap at all — only 1 room ever needed.
Constraints
- •
1 <= intervals.length <= 10^4 - •
0 <= starti < endi
Hints
Hint 1
Separate start times and end times into two SORTED arrays, then sweep: an incrementing pointer through starts, incrementing 'rooms needed' each time, but decrementing whenever an end time has already passed.
Hint 2
A min-heap of ongoing meetings' end times is an alternative, often more intuitive mental model: it directly answers 'how many rooms are currently occupied' at any point as you process meetings in start-time order.
Hint 3
Whichever technique, the answer is the MAXIMUM concurrent count observed at any point during the sweep — not the final count, and not the total number of meetings.
Solutions
public int minMeetingRooms(int[][] intervals) {
int n = intervals.length;
int[] starts = new int[n], ends = new int[n];
for (int i = 0; i < n; i++) { starts[i] = intervals[i][0]; ends[i] = intervals[i][1]; }
Arrays.sort(starts);
Arrays.sort(ends);
int rooms = 0, maxRooms = 0, endPtr = 0;
for (int startPtr = 0; startPtr < n; startPtr++) {
while (starts[startPtr] >= ends[endPtr]) { // a meeting has fully ended before this one starts
rooms--;
endPtr++;
}
rooms++;
maxRooms = Math.max(maxRooms, rooms);
}
return maxRooms;
}Time: O(n log n) · Space: O(n)