AcWing 803. 区间合并
原题链接
简单
作者:
杨樾人
,
2024-10-28 21:44:34
,
所有人可见
,
阅读 1
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<long long, long long> Interval;
int merge( vector<Interval>& intervals){
if(intervals.size() <= 1){
return intervals.size();
}
sort(intervals.begin(), intervals.end());
int ans = 1;
long long right = intervals[0].second;
for(int i=1; i<intervals.size(); i++){
auto& interval = intervals[i];
if(right >= interval.first){
right = max(right, interval.second);
continue;
}
ans++;
right = interval.second;
}
return ans;
}
int main(){
int n;
cin >> n;
vector<Interval> intervals;
intervals.reserve(n);
for(int i=0; i<n; i++){
long long a, b;
cin >> a >> b;
intervals.push_back(make_pair(a, b));
}
cout << merge(intervals) << endl;
return 0;
}