Leetcode/F家 -- 252.253 Meeting Rooms I/II(Comparator)

252.253  Meeting Rooms I/II (Comparator)

• Difficulty: Easy

 https://leetcode.com/problems/meeting-rooms/

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (s_i < e_i), determine if a person could attend all meetings.

For example,
Given [[0, 30],[5, 10],[15, 20]],
return false.

 感觉跟leetcode上面的interval那题很相似，简单一点点。
相关题Link: https://leetcode.com/problems/merge-intervals/

思路： 如果上一个会议结束时间晚于下个会议的开始时间，return false
关键词：override compactor, interval 

public class Solution {
    public boolean canAttendMeetings(Interval[] intervals) {
        if(intervals.length<=1){ return true;}
        Arrays.sort(intervals,new Comparator<Interval>(){
           //Mainly test on the comparator
           public int compare(Interval o1, Interval o2) {
               return o1.start-o2.start;
            }
        });
        for(int i=0;i<intervals.length-1;i++){
            int end = intervals[i].end;
            if(end>intervals[i+1].start){ return false;}
        }
        return true;
    }
}

---

follow up第二题 

• Difficulty: Medium

https://leetcode.com/problems/meeting-rooms-ii/ 

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (s_i < e_i), find the minimum number of conference rooms required.

For example,
Given [[0, 30],[5, 10],[15, 20]],
return 2.

Greedy解法
https://discuss.leetcode.com/topic/30274/java-ac-solution-greedy-beats-92-03/7 
Heap解法
https://discuss.leetcode.com/topic/20958/ac-java-solution-using-min-heap/2 

思路： 用minHeap存入intervals by end time，每次poll the earlist end ti,e，如和新的时间重复，再将poll的放回。存入新的结束时间。 The # left in heap is the room #.
Complexity: Space - O(N) heap

public class Solution {
    public int minMeetingRooms(Interval[] intervals) {
        if ( intervals.length < 2 ) return intervals.length;
        Arrays.sort(intervals,new Comparator<Interval>(){
            public int compare(Interval o1,Interval o2){
                return o1.start - o2.start;
            }
        });
        //min heap to track the min end time of overrlapping intervals
        PriorityQueue <Integer> heap = new PriorityQueue<Integer>();
        heap.offer(intervals[0].end);
        for (int i = 1; i<intervals.length;i++){
            int tmp = heap.poll();
            if (intervals[i].start<tmp){//if not disjoint time
                heap.offer(tmp);//need to put back since overlapping time
            }
            heap.offer(intervals[i].end);
        }
        return heap.size();
    }
}

上诉code for loop前加一个新variable room，然后每次有joint pair的情况,room++,
然后遇到disjoint pair的时候，把room重设回1

int room = 0;//设0因为第一次走loop的时候肯定会满足+1的条件
int res = 0;
for(int i=0;i<intervals.size();i++){
            //if not disjoint set
           if(intervals.get(i).start<=end){
              if(intervals.get(i).start<end){
                     room++;
              }
              end = Math.max(end,intervals.get(i).end);

           }else{      
                res+=room;
                start = intervals.get(i).start;
                end = intervals.get(i).end;
                room=1;
            }            
        }

res+=room;
return res;