253.Meeting-Rooms-II

253. 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.

代码

Approach 1: Priority Queue

Complexity Analysis
  • Time Complexity: O_(_N_log_N).
    • There are two major portions that take up time here. One is sorting of the array that takes O_(_N_log_N) considering that the array consists of N elements.
    • Then we have the min-heap. In the worst case, all N meetings will collide with each other. In any case we have N add operations on the heap. In the worst case we will have N extract-min operations as well. Overall complexity being (NlogN) since extract-min operation on a heap takes O_(log_N).
  • Space Complexity: O(_N) because we construct the min-heap and that can contain _N elements in the worst case as described above in the time complexity section. Hence, the space complexity is O_(_N).
class Solution {
public int minMeetingRooms(int[][] intervals) {
if (intervals.length == 0) {
return 0;
}
PriorityQueue<Integer> allocator = new PriorityQueue<Integer>(intervals.length, new Comparator<Integer>() {
public int compare(Integer a, Integer b) {
return a - b;
}
});
Arrays.sort(intervals, new Comparator<int[]>() {
public int compare(final int[] a, final int[] b) {
return a[0] - b[0];
}
});
allocator.add(intervals[0][1]);
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] >= allocator.peek()) {
allocator.poll();
}
allocator.add(intervals.[i][1]);
}
return allocator.size();
}
}

Approach #2 Chronological Ordering

class Solution {
public int minMeetingRooms(int[][] intervals) {
if (intervals.length == 0) {
return 0;
}
Integer[] start = new Integer[intervals.length];
Integer[] end = new Integer[intervals.length];
for (int i = 0; i < intervals.length; i++) {
start[i] = intervals[i][0];
end[i] = intervals[i][1];
}
Arrays.sort(end, new Comparator<Integer>() {
public int compare(Integer a, Integer b) {
return a - b;
}
})
Arrays.sort(start, new Comparator<Integer>() {
public int compare(Integer a, Integer b) {
return a - b;
}
});
int startPointer = 0, endPointer = 0;
int usedRooms = 0;
while (startPointer < intervals.length) {
// If there is a meeting that has ended by the time the meeting at `start_pointer` starts
if (start[startPointer] >= end[endPointer]) {
endPointer += 1;
} else {
usedRooms += 1;
}
startPointer +=1;
}
return usedRooms;
}
}