AcWing 803. 区间合并
原题链接
简单
作者:
minux
,
2020-04-22 11:25:02
,
所有人可见
,
阅读 444
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N=1e5+5;
vector<PII> INV;
int n;
int main(){
cin>>n;
for(int i=0; i<n; ++i){
int start, end;
cin>>start>>end;
INV.push_back({start, end});
}
// sort intervals
sort(INV.begin(), INV.end(), [&](PII p1, PII p2){
if(p1.first == p2.first)
return p1.second<p2.second;
return p1.first<p2.first;
});
// merge intervals
int cnt=1;
PII curINV = *INV.begin();
for(auto it = next(INV.begin()); it!=INV.end(); ++it){
if(it->first<=curINV.second) curINV.second = max(curINV.second, it->second);
else{
curINV=*it;
cnt++;
}
}
cout<<cnt<<endl;
return 0;
}