Given an array of meeting time intervals intervals where intervals[i] = [starti,
endi], return the minimum number of conference rooms required.
Example 1:
Input: intervals = [[0,30],[5,10],[15,20]] Output: 2
Example 2:
Input: intervals = [[7,10],[2,4]] Output: 1
Constraints:
1 <= intervals.length <= 1040 <= starti < endi <= 106
Solution:
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
27
28
29
/**
* Sort Input by start time.
* In a priority queue track the endtimes.
* When a new meeting occurs check the priority queue for the smallest end time of the current running meetings.
* If current start is > priority queue peek end then remove priority queue meeting and add current meeting end time.
* <p>
* Time Complexity: O(NlogN) : N is the number of meetings
* Space Complexity: O(N)
**/
class Solution {
public int minMeetingRooms(int[][] intervals) {
if (intervals.length == 0) {
return 0;
}
Arrays.sort(intervals, (a, b) -> (a[0] - b[0]));
Queue<Integer> q = new PriorityQueue<>();
q.add(intervals[0][1]);
for (int i = 1; i < intervals.length; i++) {
Integer end = q.peek();
if (intervals[i][0] >= end) {
q.poll();
}
q.add(intervals[i][1]);
}
return q.size();
}
}
