252.会议室

题目

给定一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ，请你判断一个人是否能够参加这里面的全部会议。

示例 1：
输入：intervals = [[0,30],[5,10],[15,20]]
输出：false

示例 2：
输入：intervals = [[7,10],[2,4]]
输出：true

方法

将所有的会议按照开始时间排序，之后只需要判断在一个会议开始时，上一个会议是否结束即可。

代码

public boolean canAttendMeetings(int[][] intervals) {
    if(intervals == null || intervals.length == 0)
        return true;
    Arrays.sort(intervals, (v1, v2) -> (v1[0] - v2[0]));
    for(int i = 0; i < intervals.length; i++){
        if(i - 1 >= 0 && intervals[i][0] < intervals[i - 1][1])
            return false;
    }
    return true;
}

253.会议室 II

题目

给定一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi]，为避免会议冲突，同时要考虑充分利用会议室资源，请你计算至少需要多少间会议室，才能满足这些会议安排。

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

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

方法

基本思路：
如果我们能统计出每一个时刻要开会的会议数量，就能知道各时刻对于会议室数量的需求，则会议最繁忙的那个时刻需要的会议室数量就是我们想要的结果。只要我们的会议室数量满足了这个时刻的开会要求，则其他时刻都能够满足。

算法流程：

• 因为我们要按时间顺序遍历，所以先将数组按照会议的开始时间排序
• 准备一个最小堆，堆中元素为每一个正在进行中会议的结束时间
• 遍历数组，如果发现在当前时刻，有已经过了结束时间但还在堆中的会议，便将其从堆中弹出。之后将当前的会议加入到堆中
• 在遍历过程中不断统计堆中元素的数量，这个数量代表一个时刻正在进行中的会议数量，也即对会议室数量的需求，这个需求的最大值即为结果。

代码

public int minMeetingRooms(int[][] intervals) {
    if(intervals == null || intervals.length == 0)
        return 0;
    Arrays.sort(intervals, (v1, v2) -> (v1[0] - v2[0]));
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    int meetingCount = 0;
    for(int[] meeting : intervals){
        while(!heap.isEmpty() && meeting[0] >= heap.peek())
            heap.poll();
        heap.add(meeting[1]);
        meetingCount = Math.max(meetingCount, heap.size());
    }
    return meetingCount;
}