ZYF055 最多可以参加的会议数目
大约 5 分钟贪心
ZYF055 最多可以参加的会议数目
【算法标签】 贪心
【语法标签】 :结构体(struct)、sort、自定义比较函数(cmp)、优先队列(priority_queue)、cin/cout、for循环、while循环、数组、vector
给你 n 个会议,每个会议用一个区间 表示,意思是你可以在 中的任意一天 参加这个会议。
限制:每天最多只能参加一场会议。
求:最多可以参加的会议数目。
数据范围: 不超过 ,天数范围不超过 。
二、解题思路
2.1 数据规模分析
最大 ,如果枚举所有会议的两两组合, 会超时。我们需要 或更优的算法。
2.2 为什么是贪心
想象你是一个日程很满的人,今天有好几场会议可以参加。你应该选哪一场?
直觉告诉你:选结束时间最早的那一场。因为:
- 结束晚的会议,后面还有机会参加
- 结束早的会议,今天不参加就再也没机会了
这就是本题的贪心策略核心。
2.3 算法设计
- 把所有会议按 开始时间从小到大 排序。
- 维护一个小根堆(优先队列),存放当前可以参加的会议的结束时间。堆顶永远是最早结束的会议。
- 用一个指针
i遍历排序后的会议,用一个变量d表示当前日期(从最早开始日逐渐往后推进):- 将所有 的会议的结束时间加入堆中。
- 移除堆中所有 的过期会议(这些会议已经错过了)。
- 如果堆非空,弹出堆顶(结束时间最早的会议),表示在当天 参加它,答案 。
- 往后走一天。
不一定要真的逐天遍历。我们可以用指针跳跃:把同一天开始的所有会议批量加入堆后,直接跳到堆顶会议的结束日或下一个会议的开始日。
2.4 手动模拟样例 1
输入:[[1,2], [2,3], [3,4]]
排序后(已有序):[1,2], [2,3], [3,4]
| 日期 d | 操作 | 堆内容(结束日) | 参会 | 答案 |
|---|---|---|---|---|
| 1 | 加入 [1,2] | 选结束日=2 | 1 | |
| 2 | 加入 [2,3],移除过期(无) | 选结束日=3 | 2 | |
| 3 | 加入 [3,4] | 选结束日=4 | 3 |
输出 3。
2.5 手动模拟样例 2
输入:[[1,2], [2,3], [3,4], [1,2]]
排序后:[1,2], [1,2], [2,3], [3,4](开始时间相同的按结束时间排序也可,不做要求,堆会自动处理)
| 日期 d | 操作 | 堆内容 | 参会 | 答案 |
|---|---|---|---|---|
| 1 | 加入两个 [1,2] | 选结束日=2 | 1 | |
| 2 | 加入 [2,3],移除过期的(无,但刚才参会的已弹出) | 选结束日=2 | 2 | |
| 3 | 加入 [3,4] | 选结束日=3 | 3 | |
| 4 | 无新会议 | 选结束日=4 | 4 |
输出 4。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
struct Meeting {
int st, ed; // 开始时间,结束时间
};
Meeting a[N];
bool cmp(Meeting x, Meeting y) {
return x.st < y.st; // 按开始时间升序
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i].st >> a[i].ed;
}
sort(a + 1, a + n + 1, cmp);
// 小根堆:存放当前可参加会议的结束时间
// greater<int> 让堆顶是最小值
priority_queue<int, vector<int>, greater<int>> q;
int ans = 0;
int i = 1; // 指向下一个待加入的会议
// 从最早开始的会议那天开始,逐天推进
for (int d = a[1].st; d <= N; d++) {
// 将所有开始时间 ≤ d 的会议加入堆
while (i <= n && a[i].st <= d) {
q.push(a[i].ed);
i++;
}
// 移除已经过期的会议(结束时间 < d)
while (!q.empty() && q.top() < d) {
q.pop();
}
// 如果堆非空,参加结束时间最早的会议
if (!q.empty()) {
q.pop();
ans++;
}
// 如果所有会议都处理完了且堆为空,提前结束
if (i > n && q.empty()) break;
}
cout << ans << endl;
return 0;
}上面代码逐天遍历,最坏情况下天数可能很大。更高效的写法如下(推荐):
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
struct Meeting {
int st, ed;
};
Meeting a[N];
bool cmp(Meeting x, Meeting y) {
return x.st < y.st;
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i].st >> a[i].ed;
}
sort(a + 1, a + n + 1, cmp);
priority_queue<int, vector<int>, greater<int>> q;
int ans = 0;
int i = 1;
int curDay = a[1].st; // 当前日期
while (i <= n || !q.empty()) {
// 把当前日期能开始的会议全部加入堆
while (i <= n && a[i].st <= curDay) {
q.push(a[i].ed);
i++;
}
// 移除过期的
while (!q.empty() && q.top() < curDay) {
q.pop();
}
if (!q.empty()) {
q.pop(); // 参加结束最早的
ans++;
curDay++; // 今天用了,下一天
} else {
// 堆空了但还有会议没开始,直接跳到下一个会议的开始日
if (i <= n) curDay = a[i].st;
}
}
cout << ans << endl;
return 0;
}四、复杂度分析
- 时间复杂度:。排序 ,每个会议入堆一次出堆一次,堆操作 ,总计 。
- 空间复杂度:。排序数组和堆的空间。
【知识扩展】为什么用小根堆而不是大根堆
大根堆(默认的 priority_queue<int>)堆顶是最大值,而我们需要每次选结束时间最早(即数值最小)的会议。所以必须用小根堆。
声明小根堆的方式:
priority_queue<int, vector<int>, greater<int>> q;【易错点】
- 需要及时清理过期的会议(
endDay < curDay),否则堆里可能残留无法参加的会议。 - 当堆为空但还有未开始的会议时,要跳日期,不能傻等。
- 排序时只按开始时间排即可,结束时间由堆来管理。
