LeetCode 253中等堆 · 扫描线
会议室 II 图解题解
这道题到底在问什么
给定一组会议时间 intervals，其中 intervals[i] = [starti, endi] 表示一个会议的开始和结束时间。请返回能够安排所有会议所需的最少会议室数量。
- 输入
- intervals = [[0,30],[5,10],[15,20]]
- 输出
- 2
- 输入
- intervals = [[7,10],[2,4]]
- 输出
- 1
先想最直接的笨办法
笨办法是给每间房记完整日程，来一个会议就从头扫所有房间找空位，会反复检查很多已经结束的会议。（动画第 3 步）
最优解：一步一步想明白
- 3笨办法是给每间房记完整日程，来一个会议就从头扫所有房间找空位，会反复检查很多已经结束的会议。
- 4转折：按开始时间排序，用小根堆存正在占用的房间结束时间；堆顶就是最早结束的那间，能不能复用只看它。
- 5小根堆：父 ≤ 子，最早结束时间浮到根先认识堆：它不是排好序的数组，而是一棵二叉树，最小值永远浮在树根。我们每次只看树根这一间房。
- 6intervals.sort(key=lambda x: x[0])按开始时间排序，才能在每个会议开始前，正好释放掉那些已经结束的房间。
- 7heappush(heap, 30)第一场会议来时堆是空的，直接开一间房，把结束时间 30 放进树根。
- 8heap[0]=30，30 ≤ 5 不成立5 点要开会，但树根那间房要到 30 才散，所以不能复用，必须再开一间。
- 9heappush(heap, 10)新房的结束时间 10 比旧根 30 小，自动上浮到树根。现在树有两层，同时占用 2 间房。
- 10while heap[0]=10 ≤ 15: heappop15 点开会前，先看树根 10——它早就散了，弹出它，这间房可以让给新会议。
- 11heappush(heap, 20)新会议复用了刚腾出的房间，树又是两个节点，所以同时占用的房间数没有再涨。
- 12return ans = 2答案是整个扫描过程里同时占用房间的峰值，而不是最后剩几个，更不是会议总数。
- 13[[0,30],[5,40],[10,50]] 全部重叠三场会议时间全重叠时谁也腾不出来，堆长成根加两个孩子的二叉树，根始终是最早结束的 30，答案就是 3。
- 16会议室 II 是“最小资源数 = 最大同时占用数”的代表题，堆只负责高效追踪最早结束的那间房。
- 22这是“最大重叠资源数”的原子题：往上是会议室 I 判重叠、合并区间、用机场起降；想系统刷堆与区间，去 堆专题 或 区间专题，也可以直接问小欧帮你串题。
⚠️ 容易写错的地方
✗ 错：只看上一个会议有没有结束
✓ 对：用堆盯最早结束的那间房
房间有多间，最早散场的那间才最值得复用。
✗ 错：结束时间等于开始时间也算冲突
✓ 对：heap[0] ≤ start 时就能释放
[2,4] 和 [4,8] 端点相接、不重叠，可共用一间房。
✗ 错：返回最后 heap 的长度
✓ 对：返回扫描中的最大 len(heap)
后面会议少时，结尾堆可能小于中途的峰值。
完整代码（Python / C++ / Java）
Python
import heapq
class Solution:
def minMeetingRooms(self, intervals):
intervals.sort(key=lambda x: x[0])
heap = []
ans = 0
for start, end in intervals:
while heap and heap[0] <= start:
heapq.heappop(heap)
heapq.heappush(heap, end)
ans = max(ans, len(heap))
return ansC++
class Solution {
public:
int minMeetingRooms(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end());
priority_queue<int, vector<int>, greater<int>> heap;
int ans = 0;
for (auto& it : intervals) {
while (!heap.empty() && heap.top() <= it[0]) heap.pop();
heap.push(it[1]);
ans = max(ans, (int)heap.size());
}
return ans;
}
};Java
class Solution {
public int minMeetingRooms(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
PriorityQueue<Integer> heap = new PriorityQueue<>();
int ans = 0;
for (int[] it : intervals) {
while (!heap.isEmpty() && heap.peek() <= it[0]) heap.poll();
heap.offer(it[1]);
ans = Math.max(ans, heap.size());
}
return ans;
}
}套路模板：区间并发求峰值（可背骨架）
# 区间并发峰值 = 最少资源数
items.sort(key=lambda x: x[0]) # 1) 按区间起点排序
heap = [] # 小根堆存“占用中资源”的结束点
peak = 0
for s, e in items:
while heap and heap[0] <= s: # 2) 起点前，释放已结束的资源
heapq.heappop(heap)
heapq.heappush(heap, e) # 3) 占用一个资源
peak = max(peak, len(heap)) # 4) 刷新历史最大并发
return peak// 1) 按区间起点排序
sort(items.begin(), items.end());
// 小根堆存占用中资源的结束点
priority_queue<int, vector<int>, greater<int>> heap;
int peak = 0;
for (auto& it : items) {
// 2) 起点前释放已结束的资源
while (!heap.empty() && heap.top() <= it[0]) heap.pop();
heap.push(it[1]); // 3) 占用一个资源
peak = max(peak, (int)heap.size()); // 4) 刷新峰值
}
return peak;// 1) 按区间起点排序
Arrays.sort(items, (a, b) -> a[0] - b[0]);
// 小根堆存占用中资源的结束点
PriorityQueue<Integer> heap = new PriorityQueue<>();
int peak = 0;
for (int[] it : items) {
// 2) 起点前释放已结束的资源
while (!heap.isEmpty() && heap.peek() <= it[0]) heap.poll();
heap.offer(it[1]); // 3) 占用一个资源
peak = Math.max(peak, heap.size()); // 4) 刷新峰值
}
return peak;复杂度
时间复杂度
O(n log n)
排序 O(n log n)；每个会议入堆出堆各一次，单次堆操作 O(log n)。
空间复杂度
O(n)
最坏所有会议重叠，堆这棵二叉树里有 n 个结束时间。
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 会议室 II 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
堆里维护的到底是什么？+
当前正在占用会议室的结束时间，树根是最早结束的那一间。
为什么释放用 while 而不是 if？+
同一时刻可能有好几间房都已经散场，要把树根上所有 ≤ start 的都弹干净。
不用堆还能怎么做？+
扫描线/差分：把开始记 +1、结束记 −1，按时间排序累加，峰值就是答案，同样 O(n log n)。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。