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.
GeeksforGeeks
YouTube
Input: [[0, 30], [5, 10], [15, 20]]
Output: 2
Input: [[7, 10], [2, 4]]
Output: 1
Last updated
Was this helpful?
Was this helpful?
/**
* 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;
}
}