253. Meeting Rooms II

source: https://leetcode.com/problems/meeting-rooms-ii/

Question

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

思路

这道题的思路其实和真实分配房间的思路很相似：

• 按开始的时间排序
• 每次分配一个房间，排完为止
• 继续下一次分配

其中在分配一个房间时会用上双指针的技巧。

在这里的核心其实是按开始时间排序，不然下一次会议开始的时间要大于上一次会议结束的时间，这个核心的判断逻辑是不成立的。

/**
 * @param {number[][]} intervals
 * @return {number}
 */
var minMeetingRooms = function (intervals) {
    let ret = 0;
    // 对会议开始的时间排序
    intervals.sort((a, b) => a[0] - b[0]);
    while (intervals.length) {
        // 分配一个新的会议室
        ret += 1;
        let p1 = 0;
        let p2 = 1;
        // 新会议室第一个肯定可以分配
        const remove = [p1];
        while (p2 < intervals.length) {
            const [start] = intervals[p2];
            // 下一次会议开始的时间要大于上一次会议结束的时间
            if (start >= intervals[p1][1]) {
                p1 = p2;
                remove.push(p1);
            }
            p2 += 1;
        }
        intervals = intervals.filter((_, index) => !remove.includes(index));
    }
    return ret;
};

总结

对于和分配/双指针有关的题目，排序一般是必不可少的。