AcWing 803. 区间合并-cpp
原题链接
简单
作者:
Shuken
,
2023-02-13 21:09:54
,
所有人可见
,
阅读 81
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int,int> Pll;
vector <Pll> segs;
void merge(vector<Pll> &seg){
vector<Pll>res;
sort(seg.begin(),seg.end());
int l ,r;
l = -2e9;r = -2e9;
for(auto it : seg){
if(r < it.first){ //无重合
if(l!=-2e9)
{
res.push_back({it.first,it.second});
}
l = it.first;
r = it.second;
}
//有重合
else r = max(r,it.second);
}
if(r!=-2e9)res.push_back({l,r});
segs = res;
}
int main(){
int n;
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;
return 0;
}