FB高頻

先簡歷兩個數(shù)組記錄所有的starts, ends, 然后分別排序。遍歷starts, ends,如果starts[i] < ends[end],說明這個會議在進(jìn)行，res + 1; 繼續(xù)看下一個start. 如果仍然小于現(xiàn)在這個ends[end], 說明這個新的會議開始的時候，之前的會議還在繼續(xù)，還沒結(jié)束，所以res++. 如果說新的start >= ends[end]， 說說明新的會議開始的時候，原來的會議已經(jīng)結(jié)束了，則我們不需要增加room，需要更新end到ends數(shù)組的下一個,這樣就可以求出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();
    }
}

關(guān)鍵點在于priority queue是按照end排序的，那么每次poll出來再offer進(jìn)去，排在堆頂?shù)亩际莈nd最小的，于是每一次我們都可能會延續(xù)之前的end, 可以這樣來算最小房間數(shù)目。