AcWing 803. 区间合并
原题链接
简单
作者:
Value
,
2020-04-28 11:53:33
,
所有人可见
,
阅读 532
//贪心
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
typedef pair<int, int> pii;
const int N = 100010;
pii a[N];
bool cmp(pii p, pii q){
return p.second > q.second;
}
int main(){
int n;
cin >> n;
for(int i = 0; i < n; i ++ ){
scanf("%d%d", &a[i].first, &a[i].second);
}
sort(a, a+n, cmp);
int cnt = 1;
int last = a[0].second;
for(int i = 1; i < n; i ++ ){
if(a[i].first > last){
cnt ++ ;
last = max(last, a[i].second);
}
}
cout << cnt << endl;
return 0;
}
//区间合并
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
typedef pair<int, int> pii;
const int N = 100010;
pii a[N];
int main(){
int n;
cin >> n;
for(int i = 0; i < n; i ++ ){
scanf("%d%d", &a[i].first, &a[i].second);
}
sort(a, a+n);
int cnt = 1;
int last = a[0].second;
for(int i = 1; i < n; i ++ ){
if(a[i].first > last){
cnt ++ ;
last = a[i].second;
}else{
last = max(last, a[i].second);
}
}
cout << cnt << endl;
return 0;
}