2597 无重叠区间2 (求最少删除区间数)
大约 3 分钟贪心
2597 无重叠区间2 (求最少删除区间数)
【算法标签】 贪心
【语法标签】 :结构体(struct)、sort、自定义比较函数(cmp)、for循环、cin/cout
给定一个区间集合,每个区间为 ,计算需要移除的最少区间数量,使得剩余区间两两互不重叠。
注意:仅端点接触的区间(如 [1,2] 和[2,3])视为不重叠。
输入格式
- 第一行:整数
n,表示区间个数。 - 接下来
n行:每行两个整数 和 ,表示区间的起点和终点。
输出格式
- 一个整数,表示需要移除的最少区间数量。
数据范围
二、解题思路
本题是经典的区间调度贪心问题,核心思路如下:
- 问题转化:最少移除的区间数 = 总区间数 - 最多可保留的不重叠区间数。
- 贪心策略:
- 按区间的结束位置升序排序(若结束位置相同,按起点升序排序,保证稳定性)。
- 遍历排序后的区间,每次选择结束最早且不与上一个选中区间重叠的区间。
- 该策略的核心逻辑是:每次选择结束最早的区间,能为后续区间预留最大的选择空间,从而保证选出最多的不重叠区间。
三、完整代码(C++)
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
struct Interval {
int start, end;
} intervals[N];
// 按区间结束位置升序排序
bool cmp(const Interval& a, const Interval& b) {
if (a.end != b.end) {
return a.end < b.end;
}
// 结束位置相同时,按起点升序排序(保证稳定)
return a.start < b.start;
}
int main() {
// 输入输出加速,适配n=1e5的大数据场景
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> intervals[i].start >> intervals[i].end;
}
// 按结束位置排序
sort(intervals, intervals + n, cmp);
int max_keep = 1; // 最多可保留的不重叠区间数
int last_end = intervals[0].end;
for (int i = 1; i < n; ++i) {
// 区间不重叠的条件:当前区间起点 ≥ 上一个区间终点
if (intervals[i].start >= last_end) {
max_keep++;
last_end = intervals[i].end;
}
}
// 最少移除数 = 总数 - 最多可保留数
cout << n - max_keep << endl;
return 0;
}---
四、复杂度分析
- 时间复杂度:$$O(n \log n)$$,主要开销为排序操作,遍历过程为 $$O(n)$$。
- 空间复杂度:$$O(n)$$,用于存储所有区间数据。
五、样例验证
输入
4
1 2
2 3
3 4
1 3排序后区间
[1,2]` → `[2,3]` → `[1,3]` → `[3,4]贪心选择过程
- 初始选择
[1,2],last_end = 2,max_keep = 1。 [2,3]的起点2 ≥ 2,不重叠,选择,last_end = 3,max_keep = 2。[1,3]的起点1 < 3,重叠,不选择。[3,4]的起点3 ≥ 3,不重叠,选择,max_keep = 3。
输出
4 - 3 = 1,与样例结果一致。
---
六、关键优化与注意事项
- 输入输出优化:
ios::sync_with_stdio(false); cin.tie(nullptr);可大幅提升大数据下的输入输出效率,避免超时。 - 边界处理:题目中区间端点可为负数,代码中
int类型可正常处理(范围-5e4 ~ 5e4在int表示范围内)。 - 排序稳定性:结束位置相同时按起点排序,不影响结果,但可保证排序稳定,避免因编译器实现差异导致的结果不一致。
