ZYF041 会议室
ZYF041 会议室
【算法标签】 贪心
【语法标签】 :结构体(struct)、sort、自定义比较函数(cmp)、vector、pair、优先队列(priority_queue)、cin/cout、for循环、while循环
给你 个会议的时间安排,每个会议用区间 表示。同一个会议室同一时间只能开一个会议。如果两个会议时间有重叠(端点接触不算重叠),就需要两个不同的会议室。
求:至少需要多少个会议室,才能安排下所有会议。
数据范围: 未明确给出上限(典型值 或 )。
样例:
输入:
3
0 30
5 10
15 20
输出:
2解释:会议 1()和会议 2()时间重叠,需要两个会议室。会议 2 在 10 结束,会议 3 在 15 开始,不重叠,可以复用会议 2 的会议室。所以最少需要 2 个。
二、解题思路
2.1 与前几题的区别
前几题(活动选择、无重叠区间)是选择型问题——在冲突的区间中选一部分。本题是资源分配型问题——所有会议都必须安排,求最少资源数。
本质上是问:在时间轴上,同时进行的会议数量最多是多少? 这个最大值就是最少需要的会议室数量。
2.2 方法一:优先队列(推荐给初学者)
这是最直观的方法,模拟会议室的分配过程。
思路:
- 将所有会议按开始时间从小到大排序。
- 用一个小根堆(优先队列)维护正在进行的会议的结束时间。堆顶就是最早结束的那个会议的时间。
- 遍历排序后的会议:
- 当前会议开始前,先把已经结束的会议从堆中移除(即结束时间 ≤ 当前开始时间的,说明会议室空出来了)。
- 把当前会议的结束时间加入堆(分配一个会议室给它)。
- 堆的大小就是当前同时进行的会议数,用它更新答案的最大值。
- 答案就是堆大小的历史最大值。
为什么用小根堆?
我们需要快速知道"哪个会议结束得最早",小根堆的堆顶 就能拿到最小值。
priority_queue默认是大根堆,所以需要指定greater<int>变成小根堆。
手动模拟(样例 [[0,30], [5,10], [15,20]]):
按开始时间排序后:, , (已经有序)
| 步骤 | 当前会议 | 堆(结束时间) | 堆大小 | 解释 |
|---|---|---|---|---|
| 初始 | - | 空 | 0 | - |
| 1 | 1 | 分配一个会议室,结束时间 30 入堆。ans = 1 | ||
| 2 | 2 | 堆顶 30 > 5,会议未结束,不能复用。新开会议室。ans = 2 | ||
| 3 | 2 | 堆顶 10 ≤ 15,会议 2 已结束,弹出 10。然后 20 入堆。ans = max(2, 2) = 2 |
最终需要 2 个会议室。
2.3 方法二:扫描线(差分思想)
把每个会议拆成两个事件:
- 在
start时刻,会议室需求+1 - 在
end时刻,会议室需求-1
然后按时间排序所有事件,依次扫描,累加变化量,记录最大值。
| 时刻 | 事件 | 变化 | 累计 |
|---|---|---|---|
| 0 | 开始 | +1 | 1 |
| 5 | 开始 | +1 | 2 |
| 10 | 结束 | -1 | 1 |
| 15 | 开始 | +1 | 2 |
| 20 | 结束 | -1 | 1 |
| 30 | 结束 | -1 | 0 |
最大累计值为 2,即需要 2 个会议室。
注意:扫描线方法需要小心处理"同一时刻既有开始又有结束"的情况。通常先处理结束事件(-1)再处理开始事件(+1),因为结束的会议室可以立刻复用。
三、参考代码
方法一:优先队列(小根堆)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
// 会议结构体
struct Meeting {
int start, end;
} a[N];
// 按开始时间升序排序
bool cmp(Meeting x, Meeting y) {
return x.start < y.start;
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i].start >> a[i].end;
}
// 1. 按开始时间排序
sort(a, a + n, cmp);
// 2. 小根堆:存正在进行的会议的结束时间
// greater<int> 让 priority_queue 变成小根堆
priority_queue<int, vector<int>, greater<int>> heap;
int ans = 0; // 记录堆大小的最大值
for (int i = 0; i < n; i++) {
int now_start = a[i].start;
int now_end = a[i].end;
// 释放已结束的会议室:
// 堆顶(最早结束时间) <= 当前开始时间,说明结束了
while (!heap.empty() && heap.top() <= now_start) {
heap.pop(); // 会议室空出来了
}
// 当前会议占一个会议室
heap.push(now_end);
// 更新最大同时进行的会议数
if ((int)heap.size() > ans) {
ans = heap.size();
}
}
cout << ans << endl;
return 0;
}方法二:扫描线(差分)
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
// 用一个 vector 存所有事件:pair<时间, 变化量>
// 变化量:+1 表示会议开始(需要一个会议室)
// -1 表示会议结束(释放一个会议室)
vector<pair<int, int>> events;
for (int i = 0; i < n; i++) {
int s, e;
cin >> s >> e;
events.push_back({s, 1}); // 开始事件
events.push_back({e, -1}); // 结束事件
}
// 按时间排序
// 同一时间,先处理结束事件(-1),再处理开始事件(+1)
sort(events.begin(), events.end());
int cur = 0, ans = 0;
for (auto ev : events) {
cur += ev.second; // 累加变化量
if (cur > ans) ans = cur;
}
cout << ans << endl;
return 0;
}四、复杂度分析
方法一(优先队列)
- 时间复杂度:排序 ,每个会议入堆一次、出堆一次,堆操作 ,总复杂度 。
- 空间复杂度:堆最多存 个元素,。
方法二(扫描线)
- 时间复杂度:排序 个事件,。
- 空间复杂度:存储 个事件,。
两种方法效率相当。优先队列方法更直观,模拟了"借会议室、还会议室"的过程,推荐初学者使用。扫描线方法更简洁,但需要对差分思想有一定理解。
知识扩展:priority_queue 的小根堆写法
// 大根堆(默认):堆顶是最大值
priority_queue<int> big_heap;
// 小根堆:堆顶是最小值
priority_queue<int, vector<int>, greater<int>> small_heap;三个模板参数分别是:元素类型、底层容器(默认 vector)、比较方式。
类似题目
- 活动选择(1311):在冲突中"选择"一部分,而非全部安排。
- Car Pooling(拼车):类似的扫描线问题,判断车上人数是否超载。
