253. Meeting Rooms II
Last updated
Last updated
/**
* Time complexity : O(NlogN).
* Space complexity : O(N)
*/
class Solution {
public int minMeetingRooms(int[][] intervals) {
if(intervals == null) return 0;
Arrays.sort(intervals,
Comparator.comparing((int[] interval) -> interval[0]));
PriorityQueue<Integer> heap = new PriorityQueue();
int meetingRooms = 0;
for(int[] interval: intervals) {
if(heap.isEmpty()) {
meetingRooms++;
} else {
if(interval[0] >= heap.peek()) {
heap.poll();
} else {
meetingRooms++;
}
}
heap.offer(interval[1]);
}
return meetingRooms;
}
}/**
* Time complexity : O(NlogN).
* Space complexity : O(N)
*/
class Solution {
public int minMeetingRooms(int[][] intervals) {
if(intervals == null || intervals.length == 0) return 0;
int n = intervals.length;
int[] startTimes = new int[n];
int[] endTimes = new int[n];
for(int i = 0; i < n; i++) {
startTimes[i] = intervals[i][0];
endTimes[i] = intervals[i][1];
}
Arrays.sort(startTimes);
Arrays.sort(endTimes);
int meetingRooms = 0,
endTimeIdx = 0;
for(int i = 0; i < n; i++) {
if(startTimes[i] >= endTimes[endTimeIdx]) {
endTimeIdx++;
} else {
meetingRooms++;
}
}
return meetingRooms;
}
}