AcWing 803. 区间合并
原题链接
简单
作者:
自由周某
,
2020-07-29 17:35:53
,
所有人可见
,
阅读 435
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
typedef pair<int , int > P;
bool cmp(P &a, P &b){
return a.first < b.first;
}
/*主要的思想是先把区间排序,再合并,合并的过程讲的很明了*/
void mg(vector<P> & t){
vector<P> tmp;
int i = 0;
int l = t[0].first, r = t[0].second;
for(i = 0; i < t.size()-1; i++){
if(t[i + 1].first <= r && t[i + 1].second > r) r = t[i + 1].second;
else if(t[i + 1].first > r) {
tmp.push_back({l,r});
l = t[i + 1].first;
r = t[i + 1].second;
}
}
tmp.push_back({l , r});//把最后的区间放进去
t = tmp;
}
vector<P> t;
int main(){
int n;
cin>>n;
for(int i = 0; i < n; i++) {
int l, r;
cin>> l >> r;
t.push_back({l, r});
}
sort(t.begin(), t.end(),cmp);
mg(t);
cout<<t.size()<<endl;
return 0;
}