区间合并
定义
区间合并是指将一组有重叠或相邻的区间合并成一个或多个更大的区间。
运用情况
- 图像处理：在图像的区域分析中，可能需要将相邻的具有相似特征的区域进行合并。
- 时间区间处理：比如将多个连续时间段进行合并。
- 行程规划：对一系列行程区间进行整理和合并。
- 资源分配：当涉及到对一些连续的资源区间进行整合和管理时。
- 几何计算：在一些几何问题中，对相关的区间进行合并操作以简化计算。
- 数据压缩：通过合并相似的区间来减少数据量。
- 任务调度：对任务的时间区间进行合理合并和安排。
注意事项
- 区间的表示方式：需要明确区间的表示方法，例如使用起始值和结束值来表示一个区间。
- 边界情况处理：在合并区间时，需要考虑边界情况，例如区间的起始值和结束值相等的情况。
- 区间的排序：在进行区间合并之前，通常需要对区间进行排序，以便按照一定的顺序进行合并操作。
- 结果的正确性：需要确保合并后的区间结果是正确的，并且符合预期的合并规则。
解题思路
- 对区间进行排序，以便按照起始值进行顺序处理。
- 初始化一个空的结果列表，用于存储合并后的区间。
- 遍历排序后的区间列表，对于每个区间：
- 如果结果列表为空，或者当前区间与结果列表中的最后一个区间不重叠，则将当前区间添加到结果列表中。
- 如果当前区间与结果列表中的最后一个区间重叠，则更新结果列表中最后一个区间的结束值为当前区间的结束值。
- 重复步骤 3，直到遍历完所有的区间。
- 返回合并后的区间结果列表。
Acwing.802区间和
题目描述
802. 区间和 - AcWing题库
运行代码
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
vector<PII> a;
int n,cnt=1;
bool cmp(PII &a,PII &b){
return a.first<b.first;
}
int main(){
cin>>n;
for(int i=0;i<n;i++){
int l,r;cin>>l>>r;
a.push_back({l,r});
}
sort(a.begin(),a.end(),cmp);
for(int i=1,l=a[0].first,r=a[0].second;i<a.size();i++){
if(a[i].first<=r) r=max(r,a[i].second);
else{
cnt++;
l=a[i].first;
r=a[i].second;
}
}
cout<<cnt;
return 0;
}代码思路
-
引入头文件和类型定义:使用了
<bits/stdc++.h>，这是一个非标准但常见的头文件，包含了C++标准库中的大部分内容。定义了typedef pair<int,int> PII;，将一对整数封装为一个类型，用于表示区间的左右端点。 -
变量声明:
vector<PII> a;用于存储输入的所有区间。int n, cnt = 1;其中n存储区间数量，cnt初始化为1，用于计数最终的不重叠区间数。 -
读取输入数据:读取区间总数
n，然后通过循环读取每个区间的左右端点l和r，并以pair<int, int>的形式存储到向量a中。 -
区间排序:自定义比较函数
cmp，按区间的左端点从小到大排序。使用sort(a.begin(), a.end(), cmp);对区间向量进行排序。 -
区间合并逻辑:
- 初始化两个变量
l和r，分别记录当前合并区间段的左端点和右端点，初始值为排序后第一个区间的左右端点。 - 遍历排序后的区间向量，对于每个区间，如果当前区间的左端点小于等于已合并区间的右端点，说明这两个区间重叠，此时更新合并区间的右端点为两者中较大的右端点。
- 否则，说明当前区间与已合并区间不重叠，因此计数器
cnt加1，表示又发现一个新的不重叠区间，并更新合并区间的左右端点为当前区间的端点。
- 初始化两个变量
-
输出结果:遍历结束后，输出计数器
cnt的值，即为合并后的不重叠区间个数。
改进思路
-
删除无用的
#include<bits/stdc++.h>：这是一个常用的头文件，包含了几乎所有标准库，但它不是一个标准的C++头文件，可能在某些编译环境中不可用。更推荐按需引入所需头文件，例如本例中只需<vector>和<iostream>。 -
使用
std::前缀：虽然使用了using namespace std;，但在实际项目中，避免使用整个命名空间以减少潜在的命名冲突风险。 -
变量命名：变量名可以更具描述性，如将
l和r改为left和right，提高代码可读性。 -
移除全局变量：尽量避免使用全局变量，改为在
main函数内部定义并传递给相关函数，增强代码的模块性和可维护性。 -
直接在
main中排序：由于cmp函数非常简单，且只在此处使用，可以考虑直接在sort函数调用中使用lambda表达式。
改进代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<pair<int, int>> intervals;
for (int i = 0; i < n; ++i) {
int left, right;
cin >> left >> right;
intervals.emplace_back(left, right);
}
// 直接在sort调用中使用lambda表达式简化代码
sort(intervals.begin(), intervals.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
return a.first < b.first;
});
int cnt = 1;
int prev_right = intervals[0].second;
for (int i = 1; i < n; ++i) {
if (intervals[i].first <= prev_right) {
prev_right = max(prev_right, intervals[i].second);
}
else {
++cnt;
prev_right = intervals[i].second;
}
}
cout << cnt << endl;
return 0;
}
