0253. 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.
Example 1:
Input: [[0, 30],[5, 10],[15, 20]]
Output: 2
Example 2:
Input: [[7,10],[2,4]]
Output: 1
NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.
Analysis¶
In interview for this problem, it is always a good idea to first run through an example.
Given [0, 30] [1, 5] [2, 3] [7, 10], how to allocate the rooms?
- Adding [0, 30]: Allocate first room to [0, 30].
- Adding [1, 5]: check if any room that isn't used during 1 to 5 (no existing room satisfy, so allocate another new room).
- Adding [2, 3]: do the same check as 2, but not the earliest used room now changed to room 2 (will be free on 5), but we still cannot attend the meeting because of overlap, so allocate a new room.
- Adding [7, 10]: now we check if any room that can finish the meeting earlier than 7, and we find [1, 5], so we can reuse this room for [7, 10].
Note: on step 4, why don't we just reuse [2, 3]? Yes, you can reuse that room, but there is a chance that some other interval whose start is less than 5 and greater 3 -- [4, 5]. If we reuse [2, 3], we cannot know if this new interval can be reused by [2,3] since we only keep track of the latest used room.
In order to keep track of the earliest finishing time from all the allocated room (from this we can determine if we need to allocate a new room), we can use a priority queue to keep track of all the allocated rooms' ending times (note that it will be a min-heap since we want to the smallest element from the queue). Before we add time to the priority queue, we also need to make sure that for every two intervals i and interval i + 1, interval i's start should be less or equal than interval i + 1's start, so that we can allocate in sequence in a greedy manner so that we can make sure our allocation is always the most optimal.
- Time: O(n \times \log(n)) (sort + priority queue)
- Space: O(n) for sorting and priority queue.
Code¶
int minMeetingRooms(vector<vector<int>> intervals) {
// write your solution here
auto cmp = [](vector<int>& l, vector<int>& r) {return l[0] < r[0];};
sort(intervals.begin(), intervals.end(), cmp);
priority_queue<int, vector<int>, greater<int> > pq;
for (auto i : intervals) {
if (!pq.empty() && pq.top() <= i[0]) pq.pop(); // if the earliest ending room is less than current room, we can reuse that room
pq.push(i[1]); // allocate new room
}
return pq.size();
}