253. 会议室 II

[webVueBlog]

253. 会议室 II

Description

Difficulty: 中等

Related Topics: 贪心, 数组, 双指针, 排序, 堆（优先队列）

给你一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [start_i, end_i] ，返回 所需会议室的最小数量 。

示例 1：

输入：intervals = [[0,30],[5,10],[15,20]]
输出：2

示例 2：

输入：intervals = [[7,10],[2,4]]
输出：1

提示：

• 1 <= intervals.length <= 10⁴
• 0 <= start_i < end_i <= 10⁶

Solution

Language: JavaScript

/**
 * @param {number[][]} intervals
 * @return {number}
 */
// 问题转化为：最多占用几个会议室。
// 会议开始：占用的会议室+1；会议结束：占用的会议室-1
// 例：[[0,30],[5,10],[10, 20],[15,20]]。
// 会议开始,进入会议室：[0, 1], [5, 1],[ 10, 1 ], [15, 1]
// 会议结束,离开会议室：[30, -1],[10, -1], [20, -1],[20, -1]

// 所以经过第一个循环之后得到queue：
// [[ 0, 1 ], [ 30, -1 ],[ 5, 1 ],[ 10, -1 ],[ 10, 1 ], [ 20, -1 ],[ 15, 1 ], [ 20, -1 ]]。

// 然后把它排序：如果时间相同，结束会议排在开始会议前面，也就是先结束这场会议再开始新的一场。
// 所以经过sort后得到：
// [[ 0, 1 ],[ 5, 1 ],[ 10, -1 ], [ 10, 1 ],[ 15, 1 ], [ 20, -1 ],[ 20, -1 ], [ 30, -1 ]]。
// 最后计算最多的时候有几个会议室。

// 上下车算法，把每个 start, end 分别理解成上车下车，问题就变成求最多有多少个乘客同时在车上。上车 + 1， 下车 - 1，按时间排序（如果时间相同，先下后上），求最大值。

var minMeetingRooms = function(intervals) {
    let queue = []
    for(let [start, end] of intervals) {
        queue.push([start, 1])
        queue.push([end, -1])
    }
    queue.sort((a,b) => {
        // 如果时间相同，结束会议排在开始会议前面，也就是先结束这场会议再开始新的一场。
        if(a[0]===b[0]) return a[1] - b[1]
        // 从小到大排序
        else return a[0] - b[0]
    })
    let res = 0
    let count = 0
    // 计算最多的时候有几个会议室
    for(let [time, flag] of queue) {
        count += flag
        res = Math.max(res, count)
    }
    return res
};