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.
**/
publicclassMeetingRoomsII {
classSolution {
/**
|---------|
|---------|
|-------|
|-----------|
more than one overlap
|-------|
|---------------|
|--------|
|-------| - room 1
|---------------| - room 2
|--------| - this will free room 1 and heap size is 2 again
**/
publicintminMeetingRooms(int[][] intervals) {
if(intervals.length <= 1) returnintervals.length; // 0 means no meeting room.
Arrays.sort(intervals,(a,b)->(a[0] - b[0]));//sort them by start time
PriorityQueue<int[]> minHeap = newPriorityQueue<>((a,b)->(a[1] - b[1])); // minHeap by end time
minHeap.offer(intervals[0]);//first room with min start time
intn = intervals.length;
for(inti = 1 ; i < n ; i++){
intprev[] = minHeap.peek();//last event about to end or ended
intnext[] = intervals[i];//next upcoming event
if(prev[1] <= next[0]){
// no overlap mean prev meeting ended and we have a free room for the 'next' interval
minHeap.poll();
}
//IMP : if room not free(poll) then we are increasing a count of room
// to easily understand its just count++ but its same as items remaining in minHeap