2597 无重叠区间2
大约 4 分钟贪心
2597 无重叠区间2
【算法标签】 贪心
【语法标签】 :结构体(struct)、sort、自定义比较函数(cmp)、for循环、cin/cout
给定 个区间 ,你需要移除最少数量的区间,使得剩余区间互不重叠。
注意:只在一点上接触的区间是不重叠的。例如 和 不重叠,可以同时保留。
求:最少需要移除多少个区间。
数据范围: 未明确给出上限(典型值 )。
样例:
输入:
4
1 2
2 3
3 4
1 3
输出:
1解释:移除 ,剩下 , , ,它们端点接触但不重叠,可以全部保留。移除 1 个即可。
二、解题思路
2.1 问题转化
直接想"最少移除多少个"不太直观,但换个角度:
最少移除数 = 总区间数 - 最多不重叠区间数
如果最多能保留 个不重叠的区间,那么剩下的 个就必须移除。所以问题转化为求"最多不重叠区间数"。
这恰好就是活动选择问题(1311)!因为本题规定端点接触不算重叠( 和 算不重叠),条件正好和活动选择一致。
2.2 算法步骤
- 将所有区间按照结束时间从小到大排序。
- 用一个变量
last记录上一个选中区间的结束时间,初始为 。 - 遍历排序后的区间:
- 如果当前区间的开始时间 ≥
last(即start >= last),说明不重叠,选中它,更新last = end。 - 否则,这个区间和之前选的有冲突,它就是要被移除的。
- 如果当前区间的开始时间 ≥
- 令
keep= 能保留的区间数,则答案 = $n - $keep。
2.3 三题对比
| 题目 | 端点接触是否重叠 | 求什么 | 条件 |
|---|---|---|---|
| 1311 活动选择 | 不算重叠 | 最多能选几个 | begin >= last |
| ZYF053 无重叠区间1 | 算重叠 | 最多能选几个 | begin > last |
| 2597 无重叠区间2 | 不算重叠 | 最少移除几个 | begin >= last,答案 选中数 |
可以看到,2597 的贪心部分和 1311 完全相同,只是在最后用 减去选中数量。
2.4 手动模拟样例
输入:[[1,2], [2,3], [3,4], [1,3]]
按结束时间排序后:
| 次序 | start | end |
|---|---|---|
| 1 | 1 | 2 |
| 2 | 1 | 3 |
| 3 | 2 | 3 |
| 4 | 3 | 4 |
注意:当结束时间相同时( 和 都结束于 2?不对,是 和 结束时间不同),这里情况如下:
重新排序(按 end):
| 次序 | start | end |
|---|---|---|
| 1 | 1 | 2 |
| 2 | 1 | 3 |
| 3 | 2 | 3 |
| 4 | 3 | 4 |
贪心过程(last = -0x3f3f3f3f):
- 区间 1():1 ≥ last,选中 →
keep = 1,last = 2 - 区间 2():1 ≥ 2?不成立,跳过(这个要被移除)
- 区间 3():2 ≥ 2?成立(端点接触不算重叠),选中 →
keep = 2,last = 3 - 区间 4():3 ≥ 3?成立,选中 →
keep = 3,last = 4
保留 3 个区间,移除 个。
最终答案为 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 keep = 0; // 能保留的区间数
int last = -0x3f3f3f3f; // 上一个选中区间的结束时间
for (int i = 0; i < n; i++) {
// 端点接触不算重叠,所以用 >=
if (a[i].start >= last) {
keep++;
last = a[i].end;
}
// 不满足条件的区间就是要被移除的,不需要额外处理
}
// 最少移除数 = 总数 - 最多保留数
cout << n - keep << endl;
return 0;
}四、复杂度分析
- 时间复杂度:排序 ,遍历 ,总复杂度 。
- 空间复杂度:存储 个区间的结构体数组,。
易错点
搞混三题的边界条件:
- 1311(活动选择):端点接触不冲突 →
>= - ZYF053(无重叠区间 1):端点接触冲突 →
> - 2597(本题):端点接触不冲突 →
>=,但答案 $= n - $ 选中数
- 1311(活动选择):端点接触不冲突 →
直接想"最少移除数":很多同学一上来就试图直接贪心做删除,很容易出错。最好的办法是转化成" 减去最多保留数",思路就清晰了。
last 初始值:注意用
-0x3f3f3f3f或更小的值,不能用0,因为区间起点可能为 。
类似题目
- 活动选择(1311):求"最多能安排的活动数",条件与本贪心部分一致。
- 无重叠区间 1(ZYF053):求"最多不重叠区间数",但端点接触算重叠(更严的条件)。
