ZYF053 无重叠区间1
大约 4 分钟贪心
ZYF053 无重叠区间1
【算法标签】 贪心
【语法标签】 :结构体(struct)、sort、自定义比较函数(cmp)、cin/cout、for循环、数组
给定 个区间 ,你需要选出尽可能多的区间,满足:
- 任意两个选中的区间严格不重叠。
- 重点:只在一点上接触的区间也算重叠。例如 和 在点 上接触,它们是重叠的,不能同时选。
求:最多能选出多少个区间。
数据范围: 未明确给出上限(典型值 )。
样例:
输入:
4
1 2
2 3
3 4
1 3
输出:
2解释:可以选 和 (不重叠),但不能选 和 (在点 处接触,算重叠)。
二、解题思路
2.1 与"活动选择"问题的异同
本题和经典的"活动选择问题"(1311)非常相似,都是区间调度问题,都用贪心策略。
唯一区别在于边界判定:
| 题目 | 和 的关系 | 判断条件 |
|---|---|---|
| 活动选择 | 不冲突(可以同时选) | begin >= last |
| 无重叠区间 1 | 冲突(不能同时选) | begin > last |
因此,只需要把条件从 >= 改成 > 即可。
2.2 算法步骤
- 将所有区间按照结束时间从小到大排序。
- 用一个变量
last记录上一个选中区间的结束时间,初始为 (或一个极小的数)。 - 遍历排序后的区间:
- 如果当前区间的开始时间 严格大于
last(即start > last),说明不重叠,选中它,更新last = end。 - 否则跳过。
- 如果当前区间的开始时间 严格大于
- 输出选中区间的个数。
为什么还是按结束时间排序?
无论边界怎么定义,"先结束的区间优先选"这个直觉不变。结束得越早,留给后面的空间越大。边界判定条件的改变只是把等号去掉了。
2.3 手动模拟样例
输入:[[1,2], [2,3], [3,4], [1,3]]
按结束时间排序后:
| 次序 | start | end |
|---|---|---|
| 1 | 1 | 2 |
| 2 | 1 | 3 |
| 3 | 2 | 3 |
| 4 | 3 | 4 |
注意: 和 结束时间不同但 和 结束时间相同。当结束时间相同时,按开始时间排序或保持原顺序均可,不影响最终结果。
贪心过程(初始化 last 为一个很小的数,比如 -0x3f3f3f3f):
- 区间 1():1 > last(),选中 →
ans = 1,last = 2 - 区间 2():1 > 2?不成立(1 < 2),跳过
- 区间 3():2 > 2?不成立(2 = 2,接触算重叠),跳过
- 区间 4():3 > 2?成立,选中 →
ans = 2,last = 4
最终答案为 2。
2.4 为什么不用考虑开始时间排序?
有些同学可能会想:如果两个区间结束时间相同,要不要按开始时间再排一次?
实际上,对于本题的贪心策略,结束时间相同时无论怎么排,结果都一样。因为:
- 结束时间相同的区间,你最多只能选 1 个(否则它们在结束点处重叠)。
- 选哪个对后续的影响相同(因为结束时间一样)。
所以排序时只需按结束时间排,不需要二级排序。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
// 定义区间结构体
struct Interval {
int start, end;
} a[N];
// 按结束时间升序排序
bool cmp(Interval x, Interval y) {
return x.end < y.end;
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i].start >> a[i].end;
}
// 按结束时间从小到大排序
sort(a, a + n, cmp);
int ans = 0;
// last 初始化为一个非常小的数,
// 这样第一个区间的 start > last 一定成立
int last = -0x3f3f3f3f;
for (int i = 0; i < n; i++) {
// 关键:start > last(严格大于),
// 等于也不行(端点接触算重叠)
if (a[i].start > last) {
ans++;
last = a[i].end;
}
}
cout << ans << endl;
return 0;
}四、复杂度分析
- 时间复杂度:排序 ,遍历 ,总复杂度 。
- 空间复杂度:存储 个区间的结构体数组,。
易错点
条件写成
>=而非>:这是最常见的错误。一定要看清楚题目在端点处的定义——本题是"严格不重叠",端点接触也算重叠,所以必须用>。last 的初始值:不要初始化为 ,因为区间的 start 可能为 。用
-0x3f3f3f3f(约 )或INT_MIN更安全。不要把"无重叠区间1"和"无重叠区间2"搞混:前者端点接触算重叠(
>),后者端点接触不算重叠(>=)。
类似题目
- 活动选择(1311):经典版本,端点接触不算冲突(
>=)。 - 无重叠区间 2(2597):求"最少删除区间数",且端点接触不算重叠(
>=)——是本题的"取反"版本。
