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
Example1
Input: intervals = [(0,30),(5,10),(15,20)]
Output: 2
Explanation:
We need two meeting rooms
room1: (0,30)
room2: (5,10),(15,20)
Example2
Input: intervals = [(2,7)]
Output: 1
Explanation:
Only need one meeting room
/**
* Definition of Interval:
* public classs Interval {
* int start, end;
* Interval(int start, int end) {
* this.start = start;
* this.end = end;
* }
* }
*/
public class Solution {
public int minMeetingRooms(List<Interval> intervals) {
if (intervals == null || intervals.size() == 0)
return 0;
// Sorting in ascending order of start time
Collections.sort(intervals, (a, b) -> a.start - b.start);
// Using a Min PQ
PriorityQueue<Integer> queue = new PriorityQueue<>();
int count = 1;
queue.add(intervals.get(0).end);
for (int i = 1; i < intervals.size(); i++) {
// If an overlap happens even with the smallest end interval we have
if (intervals.get(i).start < queue.peek())
count++;
else
queue.poll();
queue.add(intervals.get(i).end);
}
return count;
}
}