253.Meeting rooms II

FB高频

先简历两个数组记录所有的starts, ends, 然后分别排序。遍历starts, ends,如果starts[i] < ends[end],说明这个会议在进行，res + 1; 继续看下一个start. 如果仍然小于现在这个ends[end], 说明这个新的会议开始的时候，之前的会议还在继续，还没结束，所以res++. 如果说新的start >= ends[end]， 说说明新的会议开始的时候，原来的会议已经结束了，则我们不需要增加room，需要更新end到ends数组的下一个,这样就可以求出res.

class Solution {
    public int minMeetingRooms(Interval[] intervals) {
        int[] starts = new int[intervals.length];
        int[] ends = new int[intervals.length];  
        for (int i = 0; i < intervals.length; i++){
            starts[i] = intervals[i].start;
            ends[i] = intervals[i].end;
        }
        Arrays.sort(starts);
        Arrays.sort(ends);
        int res = 0;
        int end = 0;
        for (int i = 0; i < intervals.length; i++){
            if (starts[i] < ends[end]){
                res++;
            } else{
                end++;    
            }
        }
        return res;
    }
}

这道题还有用Priority Queue的解法，也比较有趣

     // 0    5    10   15   20   30
        // |_________________________|            
        //      |_____|
        //                |_____|


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

关键点在于priority queue是按照end排序的，那么每次poll出来再offer进去，排在堆顶的都是end最小的，于是每一次我们都可能会延续之前的end, 可以这样来算最小房间数目。