Leetcode - Meeting Rooms II

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.

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

[分析]
初始思路，使用一个变量availableTime表示当前所有已安排会议的最早结束时间，对于每个待安排会议，比较其start 和 availableTime ，若start >= availableTime ,则不冲突，无需新增新会议室，否则需要增加新会议室。考虑case：  [[1,5],[8,9],[8,9]] 就能理解该思路的bug。
由此可知仅维护一个availableTime变量不够，availableTime只能用一次。
修正bug，使用最小堆来维护所有已安排会议的结束时间，来一个新会议，仍然是比较其start 和 当前最早结束会议时间，若 start >= 最早结束时间，说明该会议可安排，就安排在最早结束那个会议的room，需要从最小堆中删除堆顶元素，将新会议的结束时间插入堆中，否则新增会议室。
思路2，参考
https://leetcode.com/discuss/50793/my-python-solution-with-explanation
原始注解：
# Very similar with what we do in real life. Whenever you want to start a meeting,
# you go and check if any empty room available (available > 0) and
# if so take one of them ( available -=1 ). Otherwise,
# you need to find a new room someplace else ( numRooms += 1 ). 
# After you finish the meeting, the room becomes available again ( available += 1 ).

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    Comparator<Interval> comparator = new Comparator<Interval>() {
        public int compare(Interval a, Interval b) { 
            return a.start - b.start;
        }
    };
    // Method -1: 初始思路，fail @ [[1,5],[8,9],[8,9]]
    public int minMeetingRooms(Interval[] intervals) {
        if (intervals == null || intervals.length == 0)
            return 0;
        Arrays.sort(intervals, comparator);
        int N = intervals.length;
        int rooms = 1;
        int availableTime = intervals[0].end; 
        for (int i = 1; i < N; i++) {
            if (intervals[i].start < availableTime) {
                rooms++;
                availableTime = Math.min(availableTime, intervals[i].end);
            }
        }
        return rooms;
    }
    // Method 1
    public int minMeetingRooms1(Interval[] intervals) {
        if (intervals == null || intervals.length == 0)
            return 0;
        Arrays.sort(intervals, comparator);
        int N = intervals.length;
        int rooms = 1;
        PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
        minHeap.offer(intervals[0].end);
        for (int i = 1; i < N; i++) {
            if (intervals[i].start < minHeap.peek()) {
                rooms++;
            } else {
                minHeap.poll();                
            }
            minHeap.offer(intervals[i].end);
        }
        return rooms;
    }
    
    // Method 2: https://leetcode.com/discuss/50793/my-python-solution-with-explanation
    public int minMeetingRooms(Interval[] intervals) {
        if (intervals == null || intervals.length == 0)
            return 0;
        int N = intervals.length;
        int[] starts = new int[N];
        int[] ends = new int[N];
        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 e = 0, rooms = 0, available = 0;
        for (int start : starts) {
            while (ends[e] <= start) {
                available++;
                e++;
            }
            if (available > 0)
                available--;
            else
                rooms++;
        }
        return rooms;
    }
}