AcWing 803. 区间合并
原题链接
简单
作者:
ls131
,
2020-05-18 14:33:15
,
所有人可见
,
阅读 436
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
using namespace std;
typedef pair<int,int>PII;
void merge(vector<PII>&segs){
vector<PII>res;
sort(segs.begin(),segs.end());
int st=-2e9,ed=-2e9;
for(auto seg: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}); //空集无穷边界被初始化过 空集也是集合的子集
segs=res;
}
int main(){
int n;
cin>>n;
vector<PII>segs; //用来存放 每一组边界 区间顺序
for(int i=0;i<n;i++){
int l,r;
scanf("%d%d",&l,&r);
segs.push_back({l,r});
}
merge (segs);
cout<<segs.size()<<endl; //应该是数pair有多少对的return
return 0;
}