Meeting Rooms II
Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...](si < ei), find the minimum number of conference rooms required.
Constraints:
- 0 <= intervals.length <= 1000
- 0 <= starti < endi <= 2^31 - 1
Examples:
Input: [[0,30],[5,10],[15,20]]
Output: 2
Explanation: We need two rooms for the meetings [0,30] and [5,10] and [15,20].
Solutions
Sorting and Priority Queue
We sort the intervals by their start times. Then we initialize a priority queue with the end time of the first interval. We iterate over the rest of the intervals. If the start time of the current interval is greater than or equal to the smallest end time in the queue, we remove that end time from the queue. Then we add the end time of the current interval to the queue. Finally, we return the size of the queue, which represents the minimum number of rooms required.
class Solution {
public:
int minMeetingRooms(vector<vector<int>>& intervals) {
if (intervals.empty()) return 0;
sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
return a[0] < b[0];
}
);
priority_queue<int, vector<int>, greater<int>> rooms;
rooms.push(intervals[0][1]);
for (int i = 1;
i < intervals.size();
i++) {
if (intervals[i][0] >= rooms.top()) {
rooms.pop();
}
rooms.push(intervals[i][1]);
}
return rooms.size();
}
}
;Follow-up:
What if we also need to find the actual rooms assigned to each meeting?
