Meeting Room II

给定一个会议时间安排的数组，每个会议时间都会包括开始和结束的时间 [[s1,e1],[s2,e2],...] (si < ei)，为避免会议冲突，同时要考虑充分利用会议室资源，请你计算至少需要多少间会议室，才能满足这些会议安排。

示例 1:

输入: [[0, 30],[5, 10],[15, 20]]
输出: 2

示例2:

输入: [[7,10],[2,4]]
输出: 1

My Solutions:

本题求需要的最少的会议室数量，其实是求同一时间点最多有多少个会议在召开，这些在某一时间点同时进行的会议是不能使用相同会议室的。因此最大同时召开会议的个数即是本题的解。

解题时，需要先按照会议的开始时间升序排序一下数组。建立一个Queue，升序保存先于自身开始的会议的结束时间。

遍历每个会议的时间段，对于任意一个当前会议，是否需要增加一间新的会议室取决于早于它开始的其他会议是否已经结束。因此，先查看Queue中其他会议的结束时间是否小于等于当前会议的开始时间，将相比于当前会议开始时间点已经结束的会议从Queue中删除，然后再将当前会议的结束时间加入到Queue中。此时Queue中保存的会议应该是在同时进行且还没有结束的所有会议，因此Queue的元素个数即是我们在此刻需要的最少会议室个数，用该个数更新全局结果的最大值。直到循环结束，返回全局最大值。

public int minMeetingRooms(int[][] intervals) {
    // 如果没有会议，直接返回0
    if(intervals.length == 0) return 0;
    
    // 按照开始时间排序数组
    Arrays.sort(intervals, (a,b) -> a[0] - b[0]);
    
    // 定义一个Queue，保存正在进行会议的结束时间
    PriorityQueue<Integer> q = new PriorityQueue<>();
    
    int max = 1; // 全局变量
    
    // 遍历每一个会议
    for (int[] in:intervals){
        // 如果当前会议的开始时间大于等于Queue中会议的结束时间
        while (q.size() > 0 && in[0] >= q.peek()){
            // 删除掉已经结束的会议
            q.poll();
        }
        // 将当前会议的结束时间加入Queue
        q.offer(in[1]);
        // 当前同时进行的会议个数为需要会议室的数量
        max = Math.max(max, q.size());
    }
    return max;
}