会议室问题

样例1

输入: intervals = [(0,30),(5,10),(15,20)]
输出: 2
解释:
需要两个会议室
会议室1:(0,30)
会议室2:(5,10),(15,20)
样例2

输入: intervals = [(2,7)]
输出: 1
解释:
只需要1个会议室就够了

/**
 * Definition of Interval:
 * public classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this.start = start;
 *         this.end = end;
 *     }
 * }
 */

public class Solution {
    /**
     * @param intervals: an array of meeting time intervals
     * @return: the minimum number of conference rooms required
     */
    public int minMeetingRooms(List<Interval> intervals) {
        Collections.sort(intervals, new Comparator<Interval>(){
            public int compare(Interval o1, Interval o2){
                if(o1.start != o2.start){
                    return o1.start - o2.start;
                }else{
                    return o1.end - o2.end;
                }
            }
        });
        // 下界
        int left = 1; 
        // 上界
        int right = intervals.size();
        while(left < right){
            int mid = left + (right - left) / 2;
            if(canSatisfy(intervals, mid)){
                right = mid;
            }else{
                left = mid + 1;
            }
        }
        return left;
    }
    public boolean canSatisfy(List<Interval> intervals, int num){
        Queue<Interval> minHeap = new PriorityQueue<>(new Comparator<Interval>(){
            public int compare(Interval o1, Interval o2){
                return o1.end - o2.end;
            }
        });
        int start = 0;
        for(int i = 0; i < num; i++){
            minHeap.add(intervals.get(i));
        }
        for(int i = num; i < intervals.size(); i++){
            // 上段时间的终止时刻，亦为当前时间段中的起始时刻
            start  = minHeap.remove().end;
            if(intervals.get(i).start < start){
                return false;
            }
            minHeap.add(intervals.get(i));
        }
        return true;
    }
}