会议室 III

标签: 数组 哈希表 排序 模拟 堆（优先队列）

难度: Hard

给你一个整数 n ，共有编号从 0 到 n - 1 的 n 个会议室。

给你一个二维整数数组 meetings ，其中 meetings[i] = [starti, endi] 表示一场会议将会在 半闭 时间区间 [starti, endi) 举办。所有 starti 的值 互不相同 。

会议将会按以下方式分配给会议室：

  1. 每场会议都会在未占用且编号 最小 的会议室举办。
  2. 如果没有可用的会议室，会议将会延期，直到存在空闲的会议室。延期会议的持续时间和原会议持续时间 相同 。
  3. 当会议室处于未占用状态时，将会优先提供给原 开始 时间更早的会议。

返回举办最多次会议的房间 编号 。如果存在多个房间满足此条件，则返回编号 最小 的房间。

半闭区间 [a, b) 是 a 和 b 之间的区间，包括 a 但 不包括 b 。

示例 1：

输入：n = 2, meetings = [[0,10],[1,5],[2,7],[3,4]]
输出：0
解释：
- 在时间 0 ，两个会议室都未占用，第一场会议在会议室 0 举办。
- 在时间 1 ，只有会议室 1 未占用，第二场会议在会议室 1 举办。
- 在时间 2 ，两个会议室都被占用，第三场会议延期举办。
- 在时间 3 ，两个会议室都被占用，第四场会议延期举办。
- 在时间 5 ，会议室 1 的会议结束。第三场会议在会议室 1 举办，时间周期为 [5,10) 。
- 在时间 10 ，两个会议室的会议都结束。第四场会议在会议室 0 举办，时间周期为 [10,11) 。
会议室 0 和会议室 1 都举办了 2 场会议，所以返回 0 。

示例 2：

输入：n = 3, meetings = [[1,20],[2,10],[3,5],[4,9],[6,8]]
输出：1
解释：
- 在时间 1 ，所有三个会议室都未占用，第一场会议在会议室 0 举办。
- 在时间 2 ，会议室 1 和 2 未占用，第二场会议在会议室 1 举办。
- 在时间 3 ，只有会议室 2 未占用，第三场会议在会议室 2 举办。
- 在时间 4 ，所有三个会议室都被占用，第四场会议延期举办。 
- 在时间 5 ，会议室 2 的会议结束。第四场会议在会议室 2 举办，时间周期为 [5,10) 。
- 在时间 6 ，所有三个会议室都被占用，第五场会议延期举办。 
- 在时间 10 ，会议室 1 和 2 的会议结束。第五场会议在会议室 1 举办，时间周期为 [10,12) 。 
会议室 1 和会议室 2 都举办了 2 场会议，所以返回 1 。

提示：

  • 1 <= n <= 100
  • 1 <= meetings.length <= 105
  • meetings[i].length == 2
  • 0 <= starti < endi <= 5 * 105
  • starti 的所有值 互不相同

Submission

运行时间: 227 ms

内存: 48.5 MB

class Solution:
    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
        cnt = [0] * n
        idle, using = list(range(n)), []
        meetings.sort(key=lambda m: m[0])
        for st, end in meetings:
            while using and using[0][0] <= st:
                heappush(idle, heappop(using)[1])
            if len(idle) == 0:
                e, i = heappop(using)
                end += e - st
            else:
                i = heappop(idle)
            cnt[i] += 1
            heappush(using, (end, i))
        ans = 0
        for i, c in enumerate(cnt):
            if c > cnt[ans]:
                ans = i
        return ans

Explain

该题解采用了优先队列（堆）来管理会议室的分配和追踪会议的结束时间。首先，将会议按照开始时间排序，以保证处理时遵循题目要求的优先级。定义两个堆，`idle` 用来存放当前空闲的会议室编号，`using` 用来存放正在使用中的会议室及其结束时间。对每场会议，首先释放所有已经结束的会议室到空闲堆中。如果此时还有空闲会议室，就分配编号最小的会议室；如果没有空闲会议室，则选择最早结束的会议室，并将当前会议延后到该会议室空闲时开始。每次会议分配后，更新会议室使用次数，并将其结束时间和编号加入使用中堆。最后，遍历使用次数数组，找到使用次数最多的会议室编号。

时间复杂度: O(m log n)

空间复杂度: O(n)

class Solution:
    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
        cnt = [0] * n  # 记录每个会议室的使用次数
        idle, using = list(range(n)), []  # 空闲和使用中的会议室堆
        meetings.sort(key=lambda m: m[0])  # 按会议开始时间排序
        for st, end in meetings:
            while using and using[0][0] <= st:  # 释放所有已结束的会议室
                heappush(idle, heappop(using)[1])
            if len(idle) == 0:  # 所有会议室被占用，需要延迟当前会议
                e, i = heappop(using)
                end += e - st  # 延长会议结束时间
            else:
                i = heappop(idle)  # 分配空闲会议室
            cnt[i] += 1  # 更新会议室使用次数
            heappush(using, (end, i))  # 将当前会议室加入使用中堆
        ans = 0
        for i, c in enumerate(cnt):
            if c > cnt[ans]:
                ans = i  # 找到使用次数最多的会议室
        return ans

Explore

在处理会议时，首先释放所有已结束的会议室是必要的，因为只有这样我们才能获得最准确的关于会议室当前状态的信息。如果不先更新会议室的状态，我们可能会错误地认为没有空闲的会议室可用，从而导致不必要的会议延误或错误的会议室分配。这种方式确保了算法能够根据实际情况做出最合理的决策。

是的，这种处理方式可能会影响到其他后续会议的安排。当所有会议室都被占用时，选择最早结束的会议室并延后当前会议的开始时间，这会导致该会议室的可用时间推迟，进而可能影响排在后面的会议。然而，这是一种权衡策略，用于在资源紧张时尽量减少对总体会议安排的影响。

在代码中，通过遍历会议室使用次数的数组并比较每个会议室的使用次数来确定使用次数最多的会议室。如果发现有多个会议室的使用次数相同，代码会保留先前找到的那个会议室的编号，因为它是首先遇到的且编号较小的。这是因为数组是按索引（即会议室编号）顺序遍历的，所以最先找到的最大计数值对应的会是最小的编号。

在所有会议室空闲时，选择哪个会议室进行分配实际上不会对算法的效率产生显著影响，因为所有会议室都可用并且等效。但在实际应用中，可能会根据会议室的物理位置或其他资源因素选择最合适的会议室。在算法实现中，通常选择编号最小的会议室，这样做是为了保持处理的一致性和简单性。