Problem description:

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:

1
2
Input: [[0, 30],[5, 10],[15, 20]]
Output: 2

Example 2:

1
2
Input: [[7,10],[2,4]]
Output: 1

Solution:

The idea of solving this question is: whenever there is a start meeting, we need to add one room.

for example, we have meetings that span along time as follows:

1
2
3
4
|_____|
      |______|
|________|
        |_______|

Then, the start time array and end time array after sorting appear like follows:

1
2
||    ||
     |   |   |  |

We can use a map to store all the position that have start or end. If there’s a start, we increase 1 on that position, means that we need a conference room. On the other hand, we decrease 1 on end, denotes that we finish using a meeting room.

Then we can use a variable to store current using meeting room, and another variable to store the peak of using meeting rooms.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    int minMeetingRooms(vector<Interval>& intervals) {
        int maxroom= 0;
        map<int, int> map; //to count
        for(auto interval: intervals){
            map[interval.start]++;
            map[interval.end]--;
        }
        int cur= 0;
        for(auto m: map){
            cur+= m.second;
            maxroom= max(maxroom, cur);
        }
        return maxroom;
    }
};

time complexity: $O(nlogn)$, map use $O(logn)$ for insertion, and n elements.
space complexity: $O(n)$

Solution 2 Heap

Thought process, always a good idea to sort meeting start time. When we go through each meeting, we want to find the earliest ended meeting so we can put another meeting after it.

We could then use a min heap to store the end time. When we see another interval.start ≥ heap.peek(), we know there’s a meeting already ended when interval meeting starts. So we can schedule the meeting after that.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[0])
        print(intervals)
        hq = [] # only put end time 
        for i in intervals:
            if hq and i[0] >= hq[0]:
                print("cur heap: ", hq)
                print("heap end: ", hq[0] , ", interval start: ", i[0])
                heapq.heapreplace(hq, i[1])
            else:
                heapq.heappush(hq, i[1])
        print(hq)
        return len(hq)
1
2
3
4
5
6
7
8
9
Example
[[0, 30], [0, 10], [3, 4], [5, 10], [6, 7], [15, 20], [30, 31]]
cur heap:  [4, 30, 10]
heap end:  4 , interval start:  5
cur heap:  [7, 10, 10, 30]
heap end:  7 , interval start:  15
cur heap:  [10, 10, 20, 30]
heap end:  10 , interval start:  30
[10, 30, 20, 31]

reference:
https://goo.gl/TQuqvR
https://goo.gl/H2uUhe