C++代码,
//区间合并,(如果两个区间有交集,就可以合并成一个区间)
#include <iostream>
#include <algorithm>
#include <vector>
/*
1.按区间左端点排序
2.扫描整个区间(两个区间的关系:1.包含2.交集3.无交集)
3.
*/
//与区间有关问题求解,大部分是贪心,不是按照左端点排序,就是按照右端点排序 ,或者双关键字排序
using namespace std;
const int N=10001;
typedef pair<int,int>PII;
vector<PII> segs;
int n;
void merge(vector<PII> &segs)//传址调用segs
{
vector<PII> res;//预存处理好的区间结果
sort(segs.begin(),segs.end());//先按照first排序,再按照second排序
int st=-2e9,ed=-2e9;//设置了两个无穷 ,等价于一个初始区间
for(auto seg:segs){//依次取出区间
if(ed<seg.first)//判断第一个区间的结尾于与下一个区间的开头哪个大 ,几判断是否有交集
{//无交集
if(st!=-2e9) res.push_back({st,ed});//已经找到一个区间 ,st!=-2e9,为了防止初始区间被存进res
st=seg.first,ed=seg.second;//读入下一个区间,将区间st=first,ed=second,
}
else ed=max(ed,seg.second);//有交集,合并区间,ed更新为这两个区间中最靠右的那个ed,循环进入下一次
}
//主体已处理完成
//处理结尾
if(st!=-2e9) res.push_back({st,ed});//最后一个区间无法与下一个区间进行对比,判断st!=-2e9为了防止segs没有区间,
//误将将初始数组加进来,故进行判断,如果不是初始数组,就存进来组后一个数组
segs=res;//将数组返回给原数组,完成
}
int main()
{
cin>>n;//输入区间个数
for(int i=0;i<n;i++){
int l,r;
cin>>l>>r;//输入区间左右端点
segs.push_back({l,r});//存进segs
}
merge(segs);//处理
cout<<segs.size()<<endl;//输出元素个数,也就是区间个数
return 0;
}