253. 会议室 II (opens new window)

Description

Difficulty: 中等

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

给你一个会议时间安排的数组 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

会议开始：占用的会议室+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 ]]。

最后计算最多的时候有几个会议室。

/**
 * @param {number[][]} intervals
 * @return {number}
 */
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
};