AcWing 803. 区间合并
原题链接
简单
作者:
码
,
2020-08-01 10:27:23
,
所有人可见
,
阅读 451
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef pair<int,int> PII;
vector<PII> segs;
void merge(vector<PII>& seg)
{
int f=-2e9,e=-2e9;
sort(seg.begin(),seg.end());//对于pair,sort优先按first排序,再按second排序
vector<PII> res;
for(int i=0;i<seg.size()-1;i++)
{
if(e<seg[i].first)//当前区间左端点<前一区间端点,一定存在一个独立区间
{
if(f!=-2e9) res.push_back({f,e});
f=seg[i].first,e=seg[i].second;
}
else e=max(e,seg[i].second);
}
if(f!=-2e9) res.push_back({f,e});
seg=res;
}
int main()
{
int n;
cin>>n;
while(n--)
{
int l,r;
cin>>l>>r;
segs.push_back({l,r});
}
merge(segs);
cout<<segs.size();
return 0;
}