1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| #include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
const int N=100010;
int nl
vector<PII> segs;
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});//区间不为空且无交集 保存结果 此结果区间判断已结束
st=seg.first,ed=seg.second;//更新当前维护的区间
}
else ed=max(ed,seg.second);//如果有交集 由之前对左端点排过序 只用比较右端点的大小 取大的哪一个到答案中
if(st!=-2e9) res.push_back({st,ed}); //循环结束时st ed是最后一个序列 不需要继续维护了 直接加到res数组里
segs=res;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
int l,r;
cin>>l>>r;
segs.push_back({l,r});
}
merge(segs);
cout<<segs.size()<<endl;
}
|
