1311 活动选择
大约 4 分钟贪心
1311 活动选择
【算法标签】 贪心
【语法标签】 :结构体(struct)、sort、自定义比较函数(cmp)、for循环、cin/cout、数组
学校有 个活动,每个活动有起始时间 和结束时间 ()。同一时间礼堂只能被一个活动使用,也就是说选中的活动之间不能有时间上的重叠。
求:最多能安排多少个活动。
数据范围:。
样例:11 个活动,按贪心策略最多安排 4 个。
二、解题思路
2.1 数据规模分析
,数据量很小。即使 的算法也只有 级别,完全可行。但我们可以用贪心做到 ,主要消耗在排序上。
2.2 为什么是贪心?
直觉上,我们肯定希望每次选一个结束得最早的活动,这样留给后面活动的时间就最多。
举一个简单的例子:假设有两个活动 A[1, 10] 和 B[5, 6]。如果选了 A,就只能安排 1 个活动;如果选了 B,B 结束后还有大量时间可以安排别的活动。显然选 B 更好。
这就是"结束时间越早越优先"的贪心策略。
2.3 算法步骤
- 将所有活动按照结束时间从小到大排序。
- 用一个变量
last记录上一个选中活动的结束时间,初始为 (或 )。 - 遍历排序后的活动:
- 如果当前活动的开始时间
last,说明它和上一个选中的活动不冲突,选中它,并更新last为这个活动的结束时间。 - 否则跳过。
- 如果当前活动的开始时间
- 输出选中活动的个数。
为什么按结束时间排序而不是按开始时间?
如果按开始时间排序,你可能会选一个开始早但持续时间很长的活动,占用了大量时间。而按结束时间排序能保证每次选的都是"最不碍事"的活动。
2.4 手动模拟样例
假设有 11 个活动(样例数据):
| 活动 | 开始 | 结束 |
|---|---|---|
| 1 | 1 | 4 |
| 2 | 3 | 5 |
| 3 | 0 | 6 |
| 4 | 5 | 7 |
| 5 | 3 | 8 |
| 6 | 5 | 9 |
| 7 | 6 | 10 |
| 8 | 8 | 11 |
| 9 | 8 | 12 |
| 10 | 2 | 13 |
| 11 | 12 | 14 |
按结束时间排序后:
| 次序 | 活动 | 开始 | 结束 |
|---|---|---|---|
| 1 | 1 | 1 | 4 |
| 2 | 2 | 3 | 5 |
| 3 | 3 | 0 | 6 |
| 4 | 4 | 5 | 7 |
| 5 | 5 | 3 | 8 |
| 6 | 6 | 5 | 9 |
| 7 | 7 | 6 | 10 |
| 8 | 8 | 8 | 11 |
| 9 | 9 | 8 | 12 |
| 10 | 10 | 2 | 13 |
| 11 | 11 | 12 | 14 |
贪心过程:
last = 0- 活动 1:开始 1 ≥ 0,选中 →
ans = 1,last = 4 - 活动 2:开始 3 < 4,冲突,跳过
- 活动 3:开始 0 < 4,冲突,跳过
- 活动 4:开始 5 ≥ 4,选中 →
ans = 2,last = 7 - 活动 5:开始 3 < 7,冲突,跳过
- 活动 6:开始 5 < 7,冲突,跳过
- 活动 7:开始 6 < 7,冲突,跳过
- 活动 8:开始 8 ≥ 7,选中 →
ans = 3,last = 11 - 活动 9:开始 8 < 11,冲突,跳过
- 活动 10:开始 2 < 11,冲突,跳过
- 活动 11:开始 12 ≥ 11,选中 →
ans = 4,last = 14
最终答案为 4。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
// 定义活动结构体
struct Act {
int begin, end;
} a[N];
// 按结束时间升序排序
bool cmp(Act x, Act y) {
return x.end < y.end;
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i].begin >> a[i].end;
}
// 按结束时间从小到大排序
sort(a, a + n, cmp);
int ans = 0; // 选中的活动数量
int last = 0; // 上一个选中活动的结束时间
for (int i = 0; i < n; i++) {
// 当前活动的开始时间 ≥ 上一个的结束时间,说明不冲突
if (a[i].begin >= last) {
ans++;
last = a[i].end;
}
}
cout << ans << endl;
return 0;
}四、复杂度分析
- 时间复杂度:排序 ,遍历 ,总复杂度 。对于 来说非常快。
- 空间复杂度:存储 个活动的结构体数组,。
知识扩展:贪心策略的证明思路
本题是最经典的"活动选择问题"(Activity Selection Problem)。贪心策略的正确性可以用交换论证(Exchange Argument)来证明:
假设存在一个最优解,如果我们把最优解中结束时间不是最早的那个活动,替换成结束时间最早的活动,不会使解变差。重复这个替换,最终得到的就是贪心解。因此贪心解一定是最优的。
类似题目
- 无重叠区间 1(ZYF053):和本题几乎一样,但注意端点重叠也算重叠。
- 无重叠区间 2(2597):求的是"最少删除区间数",等价于 减去本题答案。
