LeetCode 题解工作台
会议室 III
给你一个整数 n ，共有编号从 0 到 n - 1 的 n 个会议室。 给你一个二维整数数组 meetings ，其中 meetings[i] = [start i , end i ] 表示一场会议将会在 半闭 时间区间 [start i , end i ) 举办。所有 start i 的值 互不相…
5
题型
5
代码语言
3
相关题
当前训练重点
困难 · 数组·哈希·扫描
答案摘要
我们定义两个优先队列，分别表示空闲会议室、使用中的会议室。其中：空闲会议室 依据下标排序；而使用中的会议室 依据结束时间、下标排序。 先对会议按照开始时间排序，然后遍历会议，对于每个会议：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个整数 n ，共有编号从 0 到 n - 1 的 n 个会议室。
给你一个二维整数数组 meetings ，其中 meetings[i] = [starti, endi] 表示一场会议将会在 半闭 时间区间 [starti, endi) 举办。所有 starti 的值 互不相同 。
会议将会按以下方式分配给会议室：
- 每场会议都会在未占用且编号 最小 的会议室举办。
- 如果没有可用的会议室，会议将会延期，直到存在空闲的会议室。延期会议的持续时间和原会议持续时间 相同 。
- 当会议室处于未占用状态时，将会优先提供给原 开始 时间更早的会议。
返回举办最多次会议的房间 编号 。如果存在多个房间满足此条件，则返回编号 最小 的房间。
半闭区间 [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 <= 1001 <= meetings.length <= 105meetings[i].length == 20 <= starti < endi <= 5 * 105starti的所有值 互不相同
解题思路
方法一：优先队列（小根堆）
我们定义两个优先队列，分别表示空闲会议室、使用中的会议室。其中：空闲会议室 依据下标排序；而使用中的会议室 依据结束时间、下标排序。
先对会议按照开始时间排序，然后遍历会议，对于每个会议：
- 若有使用中的会议室小于当前等于会议的开始时间，将其加入到空闲会议室队列 中；
- 若当前有空闲会议室，那么在空闲队列 中取出权重最小的会议室，将其加入使用中的队列 中；
- 若当前没有空闲会议室，那么在使用队列 中找出最早结束时间且下标最小的会议室，重新加入使用中的队列 中。
时间复杂度 ，空间复杂度 ，其中 和 分别为会议室数量和会议数量。
相似题目：
class Solution:
def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
meetings.sort()
busy = []
idle = list(range(n))
heapify(idle)
cnt = [0] * n
for s, e in meetings:
while busy and busy[0][0] <= s:
heappush(idle, heappop(busy)[1])
if idle:
i = heappop(idle)
cnt[i] += 1
heappush(busy, (e, i))
else:
a, i = heappop(busy)
cnt[i] += 1
heappush(busy, (a + e - s, i))
ans = 0
for i, v in enumerate(cnt):
if cnt[ans] < v:
ans = i
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(M \cdot \log M + M \cdot \log N + N \cdot \log N) where M is the number of meetings and N is the number of rooms due to sorting and heap operations. Space complexity is O(N + sort) for the heap and the room counters. |
| 空间 | O(N + sort) |
面试官常问的追问
外企场景- question_mark
Focus on array scanning plus hash lookup for efficient room tracking.
- question_mark
Sort meetings before processing to avoid misallocation under overlap conditions.
- question_mark
Consider edge cases where multiple meetings finish simultaneously and tie-breaking matters.
常见陷阱
外企场景- error
Forgetting to delay meetings when all rooms are busy.
- error
Using a linear search for free rooms instead of a heap leading to TLE.
- error
Not breaking ties correctly when multiple rooms have the same maximum meeting count.
进阶变体
外企场景- arrow_right_alt
Return the earliest time a specific room is free after all meetings.
- arrow_right_alt
Count the total delay time accumulated by all meetings.
- arrow_right_alt
Determine which room holds the least meetings instead of the most.