[LeetCode] 253. Meeting Rooms II

Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.

Example 1:
Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2

Example 2:
Input: intervals = [[7,10],[2,4]]
Output: 1

Constraints:
1 <= intervals.length <= 104
0 <= starti < endi <= 106

会议室 II。

给你一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ，返回所需会议室的最小数量。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/meeting-rooms-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路一 - 排序 + 双指针

第一种是排序 + 双指针。具体做法是把每个会议的开始时间和结束时间拎出来分别排序，再遍历 intervals。遍历的时候，设置一个 pointer = 0，判断当前 interval[i] 的开始时间是否大于前一个会议的结束时间 interval[pointer][end]。如果大于，就说明不需要新开一个会议室；如果小于，就需要新开一个会议室。因为题目只在意需要同时开几个会议室，所以 start 和 end 可以分别排序。end 只要结束一个，就意味着同时需要的会议室就少一个。

如果扫描线的题目做多了，一开始的本能反应可能是对 start 或者对 end 排序，看看是否存在 interval 之间的 overlap，但是其实是行不通的，因为可能存在比如某个会议 start 时间没有跟其他任何一个会议的 end 时间有冲突，但是有可能这个会议一直持续到最后，他的 end 时间跟别的会议也没有 overlap，但是他其实一直是占用一个房间的。

同时，为什么排序 + 双指针这个做法是正确的呢？对 start 和对 end 分别排序之后，因为 start 和 end 是有序的，在用双指针分别指向当前的 start 和当前的 end 的时候，只要当前 start 小于当前的 end，就一定要再开一个房间，因为当前确实是有一个会议没有结束。我们将 start 和 end 分别排序之后，其实是可以把数据抽象成如下这幅图的。

一开始，会议时间线是这样的：

|_____|
      |______|
|________|
        |_______|

如果把开始时间和结束时间分别排序，会变成：

1 2	`\|\| \|\| \| \| \| \|`

所以只要碰到 start，就一定要增加一个房间，碰到 end 就可以减少一个房间。我们在遍历的过程中找到同时使用的会议室的峰值即可。

复杂度

时间O(nlogn) - 因为有对 input 排序
空间O(n) - 有用额外数组对 start 和 end 排序

代码

JavaScript实现

/**
 * @param {number[][]} intervals
 * @return {number}
 */
var minMeetingRooms = function(intervals) {
    let start = [];
    let end = [];
    let len = intervals.length;
    for (let i = 0; i < len; i++) {
        let cur = intervals[i];
        start.push(cur[0]);
        end.push(cur[1]);
    }
    start = start.sort((a, b) => a - b);
    end = end.sort((a, b) => a - b);
    let res = 0;
    let pointer = 0;
    for (let i = 0; i < len; i++) {
        if (start[i] < end[pointer]) {
            res++;
        } else {
            pointer++;
        }
    }
    return res;
};

Java实现

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        // corner case
        if (intervals == null || intervals.length == 0) {
            return 0;
        }
        // normal case
        int len = intervals.length;
        int[] start = new int[len];
        int[] end = new int[len];
        for (int i = 0; i < len; i++) {
            start[i] = intervals[i][0];
            end[i] = intervals[i][1];
        }
        Arrays.sort(start);
        Arrays.sort(end);
        int res = 0;
        int pointer = 0;
        for (int i = 0; i < len; i++) {
            if (start[i] < end[pointer]) {
                res++;
            } else {
                pointer++;
            }
        }
        return res;
    }
}

思路二 - 最小堆

先对 intervals 按开始时间排序，再用一个最小堆存放每个 interval 的结束时间，并加入第一个 interval，此时堆顶是第一个 interval 的结束时间。遍历 intervals，判断当前 interval 的开始时间（A）跟堆顶 interval 的结束时间（B），若 A >= B 则说明两个 interval 没有 overlap，B 可以被弹出，A 放入堆中；若 A < B，说明 B 那场会议还未结束，B 不能弹出，A 还是要放入堆中。最后堆的 size 就是所需的会议室数量。

复杂度

时间O(nlogn)，其中排序O(nlogn)，heap的各项操作O(logn)
空间O(n)

代码

Java实现

class Solution {
    public int minMeetingRooms(int[][] intervals) {
		// 按开始时间排序
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
		// 堆顶是结束时间最小的会议
        PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> a - b);
        int n = intervals.length;
        for (int i = 0; i < n; i++) {
            int[] cur = intervals[i];
            if (!queue.isEmpty() && queue.peek() <= cur[0]) {
                queue.poll();
            }
            queue.offer(cur[1]);
        }
        return queue.size();
    }
}

[LeetCode] 253. Meeting Rooms II

思路一 - 排序 + 双指针

复杂度

代码

思路二 - 最小堆

复杂度

代码

相关题目