package com.freetymekiyan.algorithms.level.medium;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * 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.
 * <p>
 * For example,
 * Given [[0, 30],[5, 10],[15, 20]],
 * return 2.
 * <p>
 * Company Tags: Google Facebook
 * Tags: Heap, Greedy, Sort
 * Similar Problems: (H) Merge Intervals, (E) Meeting Rooms
 */
public class MeetingRooms2 {

    public class Solution {

        /**
         * Sort, heap, greedy.
         * Always put the next starting meeting after the first ending meeting.
         * If the start time overlaps with the nearest end time, need a new room.
         * So, sort the meetings according to start time first.
         * Then for each interval in the array:
         * 1) If min heap is empty, add to heap directly.
         * 2) Compare with the min ending time, if doesn't overlap, add this meeting after.
         * 3) If overlap, need a new room.
         */
        public int minMeetingRooms(Interval[] intervals) {
            if (intervals == null || intervals.length == 0) {
                return 0;
            }
            Arrays.sort(intervals, (a, b) -> a.start - b.start);
            PriorityQueue<Interval> minHeap = new PriorityQueue<>(intervals.length, (a, b) -> a.end - b.end);
            for (Interval i : intervals) {
                if (!minHeap.isEmpty() && i.start >= minHeap.peek().end) {
                    minHeap.poll();
                }
                minHeap.add(i);
            }
            return minHeap.size();
        }
    }

    /**
     * Interval class provided by leetcode.
     */
    public class Interval {

        int start;
        int end;

        Interval() {
            start = 0;
            end = 0;
        }

        Interval(int s, int e) {
            start = s;
            end = e;
        }
    }
}

@@ -514,41 +514,8 @@
  %7B%0A%0A
-    public class Solution %7B%0A%0A    
     
@@ -527,38 +527,30 @@
     
-  
-  
 * Sort
-, heap, g
+. Heap. G
 reedy.%0A
-    
     
@@ -626,20 +626,16 @@
 g.%0A     
-    
 * If the
@@ -704,20 +704,16 @@
 m.%0A     
-  
-  
 * So, so
@@ -764,20 +764,16 @@
 t.%0A     
-    
 * Then f
@@ -812,16 +812,11 @@
     
- 
-   * 1)
+* %7C
  If 
@@ -831,188 +831,179 @@
  is 
+not 
 empty
-, add to heap directly.%0A         * 2) Compare with the min ending time, if doesn't overlap, add this meeting after.%0A         * 3) If overlap, need a new room
+ or start time doesn't overlap with first ending time:%0A     * %7C   Poll first ending time from the heap.%0A     * %7C Add the ending time for current meeting
 .%0A     
- 
-   */%0A    
+*/%0A
     
@@ -1057,28 +1057,24 @@
 ) %7B%0A        
-    
 if (interval
@@ -1119,28 +1119,24 @@
             
-    
 return 0;%0A  
@@ -1141,32 +1141,26 @@
         
-    %7D%0A  
+%7D%0A
         
   Arrays
@@ -1151,18 +1151,16 @@
         
-  
 Arrays.s
@@ -1175,26 +1175,29 @@
 rvals, (
-a, b
+i1, i2
 ) -%3E 
-a
+i1
 .start -
@@ -1197,17 +1197,18 @@
 start - 
-b
+i2
 .start);
@@ -1208,20 +1208,16 @@
 start);%0A
-    
         
@@ -1238,21 +1238,21 @@
 Inte
-rval%3E minHeap
+ger%3E firstEnd
  = n
@@ -1274,56 +1274,11 @@
 e%3C%3E(
-intervals.length, (a, b) -%3E a.end - b.end);%0A    
+);%0A
     
@@ -1328,24 +1328,21 @@
     
-  
-  
 if (!
-minHeap
+firstEnd
 .isE
@@ -1366,26 +1366,23 @@
  %3E= 
-minHeap
+firstEnd
 .peek()
-.end
 ) %7B%0A
@@ -1397,27 +1397,24 @@
         
-    minHeap
+firstEnd
 .poll();
@@ -1410,28 +1410,24 @@
 End.poll();%0A
-    
             
@@ -1444,25 +1444,26 @@
     
-    minHeap
+firstEnd
 .add(i
+.end
 );%0A 
@@ -1465,34 +1465,26 @@
 d);%0A        
-  
-  %7D%0A    
+%7D%0A
         retu
@@ -1490,33 +1490,24 @@
 urn 
-minHeap.size();%0A        %7D
+firstEnd.size();
 %0A   

update Meeting Rooms 2