AcWing 803. 区间合并
原题链接
简单
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef pair<int,int> PII; // 定义一个pair类型,命名为PII,用于存储区间的起点和终点
const int N=100010; // 定义常量N,表示可能的最大区间数
int n; // 变量n表示区间的数量
vector<PII> segs; // 用于存储输入的区间 segs 是 "segments" 的缩写,表示一组区间或线段
// 合并区间的函数
void merge(vector<PII> &segs)
{
vector<PII> res; // 用于存储合并后的区间
/*
sort 函数会使用元素的 < 运算符进行比较。在 vector<PII> 中,每个元素是一个 pair<int, int>,
排序时会首先比较 pair 的第一个元素(即区间的起点);如果第一个元素相同,
则比较第二个元素(即区间的终点)。
因此,这行代码的作用是将 segs 容器中的所有区间按照起点从小到大的顺序排序,
如果起点相同,则按照终点从小到大的顺序排序
*/
sort(segs.begin(),segs.end()); // 先将区间按起点进行排序
int st=-2e9, ed=-2e9; // 初始化起点和终点为一个非常小的值
for(auto seg:segs) //遍历 segs 容器中的每一个区间(每个 pair<int, int>),并在每次迭代中将当前区间赋值给变量 seg
if(ed<seg.first) // 如果当前区间的起点在上一个区间的终点之后
{
if(st!=-2e9) res.push_back({st,ed}); // 如果起点不为初始值,说明有一个有效的区间,将其添加到结果中
st=seg.first, ed=seg.second; // 更新起点和终点为当前区间
}
else ed=max(ed,seg.second); // 如果有重叠或相邻的区间,更新终点为两者中的较大值
if(st !=-2e9) res.push_back({st,ed}); // 如果还有未处理的区间,添加到结果中
segs=res; // 将合并后的区间赋值回原来的区间容器
}
int main()
{
cin >> n; // 输入区间的数量
for(int i=0; i<n; i++)
{
int l, r; // l表示区间的起点,r表示区间的终点
cin >> l >> r; // 输入每个区间
segs.push_back({l,r}); // 将输入的区间存储在segs中
}
merge(segs); // 调用合并函数
cout << segs.size() << endl; // 输出合并后区间的数量
return 0;
}