ZYF053 无重叠区间1(求最多可保留区间数)
大约 4 分钟贪心
ZYF053 无重叠区间1(求最多可保留区间数)
【算法标签】 贪心
【语法标签】 :结构体(struct)、sort、自定义比较函数(cmp)、cin/cout、for循环、数组
给定一个区间的集合,共 n 个区间,每个区间表示为 [start_i, end_i]。请选出最多数量的区间,使得任意两个选中的区间严格不重叠(前一个区间的结束点不能等于后一个区间的起点,仅在一点上接触也视为重叠,例如 [1,2] 和 [2,3] 是重叠的)。求最多能选多少个区间。
数据范围:
二、解题思路(贪心算法)
核心思想
区间调度问题的最优策略是贪心选择最早结束的区间:
- 每次选择结束时间最早的区间,这样能给后续的区间留出尽可能多的空间,从而能选出更多的不重叠区间。
- 本题的特殊点是:区间端点接触也视为重叠,因此下一个区间的起点必须严格大于上一个区间的终点。
解题步骤
输入数据:读取区间总数
n,并存储每个区间的起点和终点。排序区间:将所有区间按结束时间升序排序;若结束时间相同,则按起点升序排序,保证算法稳定性。
贪心选择:
- 初始化选择第一个区间(结束时间最早的区间),记录其结束时间。
- 遍历后续所有区间,若当前区间的起点严格大于上一个选中区间的结束时间,则选择该区间,并更新结束时间。
输出结果:最终选中的区间数量即为答案。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
// 定义区间结构体,包含起点和终点
struct Node{
int start, end;
} a[N];
// 自定义排序规则:按区间结束位置升序排序
bool cmp(Node x, Node y){
if (x.end != y.end){
return x.end < y.end;
}
// 结束位置相同时,按起点升序排序(保证稳定性)
return x.start < y.start;
}
int main(){
int n;
cin >> n;
// 读取所有区间
for (int i = 1; i <= n; i++){
cin >> a[i].start >> a[i].end;
}
// 按结束时间升序排序
sort(a + 1, a + n + 1, cmp);
// cnt: 选中的区间数量,初始为1(第一个区间必然被选中)
int cnt = 1;
// last_end_time: 记录上一个选中区间的结束时间
int last_end_time = a[1].end;
// 从第二个区间开始遍历
for(int i = 2; i <= n; i++){
// 当前区间的起点严格大于上一个区间的终点,才可以选择
if (a[i].start > last_end_time){
cnt++;
// 更新上一个区间的结束时间为当前区间的结束时间
last_end_time = a[i].end;
}
}
// 输出最多可选中的区间数量
cout << cnt;
return 0;
}四、算法复杂度
时间复杂度:
- 排序操作的时间复杂度为 ,遍历区间的时间复杂度为 ,整体由排序主导。
空间复杂度:
- 需要数组存储所有区间信息,空间复杂度为线性。
该复杂度可以完全满足题目中 的数据规模要求。
五、样例验证过程
样例输入
4
1 2
2 3
3 4
1 3步骤 1:排序区间
按结束时间升序排序后,区间顺序为:
[1,2](end=2)、[1,3](end=3)、[2,3](end=3)、[3,4](end=4)
步骤 2:贪心选择
- 初始选择
[1,2],cnt=1,last_end_time=2。 - 遍历
[1,3]:起点1不大于2,不选。 - 遍历
[2,3]:起点2不大于2,不选。 - 遍历
[3,4]:起点3 > 2,选中,cnt=2,last_end_time=4。
最终结果
选中的区间为 [1,2] 和 [3,4],共 2 个,与样例输出一致。
总结
- 本题是经典的区间调度贪心问题,核心策略是 “优先选结束最早的区间”。
- 关键细节:区间端点接触也视为重叠,因此判断条件为
当前区间起点 > 上一个区间终点。 - 算法高效简洁,时间复杂度由排序主导,能轻松处理大规模数据。
