LC253. Meeting Rooms II

public int minMeetingRooms(int[][] intervals) {
        if (intervals == null || intervals.length == 0) return 0;
        Arrays.sort(intervals, new Comparator<int[]>(){
            public int compare(int[] a, int[] b) {
                return a[0] - b[0];
            }
        });
        
        PriorityQueue<int[]> pq = new PriorityQueue(intervals.length, new Comparator<int[]>(){
            public int compare(int[] a, int[] b) {
                return a[1] - b[1];
            }
        });
        
        pq.offer(intervals[0]);
        for (int i = 1; i < intervals.length; ++i) {
            int[] interval = pq.poll();
            if (interval[1] <= intervals[i][0]) {
                interval[1] = intervals[i][1];
            }else pq.offer(intervals[i]);
            
            pq.offer(interval);
        }
        return pq.size();
    }

1. Arrays.sort()把数组按照start时间先后顺序排序
2. Priority Queue存入按照end时间先后顺序排序的区间
3. 两个meeting，实际上比较的是start时间早些的A的end时间和后面一个start时间的B的开始的时间，如果不重叠就可以合并这两个区间，重叠就必须两个room;
4. pq中先offer的总是两个meeting中后面的那个，下次poll直接得到这个

interval[1] = intervals[i][1]

合并的理由: 新的meeting总是需要一个新的会议室，但是此时看看前面的interval[1]和当前的区间的结尾时间intervals[i][1]看能不能重用之前的room，如果可以直接合并结尾时间，并不用新增加room

深入思考if else部分

if (interval[1] <= intervals[i][0]) {
    interval[1] = intervals[i][1];
}else pq.offer(intervals[i]);

pq.offer(interval);

1. 如果A结尾时间早于B开头时间，那么1个room就行了，合并之后interval放入`pq;
2. 如果A结尾时间并没有早于B开头，那么A和B有重叠，因为是pq,所以A和B放进去的顺序都无所谓，反正肯定会按照end时间先后顺序放进去；为什么放两个？因为A和B的结尾时间的先后顺序不确定，此时两个都要看来判断end时间靠后的那个区间是哪一个

为什么想到用PriorityQueue

1. 因为这里每次检测完interval之后每个区间都要用end时间先后顺序排序，而且是时时保持这个顺序；
2. 并不是像前面Arrays.sort()那样，一次sort完成之后就行了，这一堆区间的结果集时刻都要保持是按照end时间的现货顺序排列的，所以想到用PQ