AcWing 803. 区间合并
原题链接
简单
作者:
派小星
,
2020-09-01 12:24:29
,
所有人可见
,
阅读 305
//1、对左端点进行排序
//2、分类讨论:相离,相交,内含
#include<iostream>
#include<algorithm>
using namespace std;
typedef pair<int,int> pii;
const int N=1e5+10,minn=-1e9;
vector<pii> segs;
//传引用
void merge(vector<pii> &segs)
{
//合并后的区间
vector<pii> res;
//将左右端点都初始化为无穷小
int l=minn,r=minn;
//遍历segs数组
for(auto seg:segs)
{
//如果第一个区间右端点小于第二个区间的左端点,则相离
if(r<seg.first)
{
//如果r不是第一次,则把第一个区间加入
if(r!=minn) res.push_back({l,r});
//让l和r变成第二个区间的的左右端点
l=seg.first,r=seg.second;
}
else
{
//内含或者相交,因为左端点一定是第一个区间最小,那么找出最大的右端点
r=max(r,seg.second);
}
}
//把最后一个区间加进去
res.push_back({l,r});
//把res赋值给segs
segs=res;
}
int main()
{
int n;
cin>>n;
//输入n个区间并加入到segs
for(int i=0;i<n;i++)
{
int l,r;
cin>>l>>r;
segs.push_back({l,r});
}
//对区间左端点进行排序,segs默认按第一个参数进行排序
sort(segs.begin(),segs.end());
//调用合并区间的函数,输出区间的长度
merge(segs);
cout<<segs.size()<<endl;
return 0;
}