AcWing 803. 区间合并
原题链接
简单
作者:
QingQingDE
,
2021-08-26 15:25:04
,
所有人可见
,
阅读 185
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int>PII;
void merge(vector<PII> &segs){
vector<PII>res;
sort(segs.begin(), segs.end());//对sges进行排序,在pair为数据基础的情况下,有限按first排序,相当于按每个区间的左端点进行排序
int st = -2e9, ed = -2e9;
for(auto seg : segs){//遍历segs容器
if(ed < seg.first){ //如果当前进行操作的区间的最右端小于枚举的区间的最左端,证明两个区间没有交集,不能合并
if(st != -2e9) res.push_back({st, ed});//如果当前区间不是初始化的操作区间,将当前区间存入res中
st = seg.first;
ed = seg.second;
//将当前枚举的区间更新为当前进行操作的区间
}
else ed = max(ed, seg.second);//如果两个区间有交集,就将当前操作的区间右端点更新为最右端的点,相当于两个区间合并
}
if(st != -2e9) res.push_back({st, ed});//将最后一个区间放入res,同时防止输入的区间为空
segs = res;//把答案赋给segs
}
int main()
{
int n;
cin>>n;
vector<PII>segs;
for(int i = 0; i < n; i ++ ){
int l, r;
cin>>l>>r;
segs.push_back({l, r});//将区间存入容器内
}
merge(segs);
cout<<segs.size()<<endl;//输出容器内的元素个数,即合并后的区间个数
return 0;
}