分析过程
(y总nb)
第一步:按区间右端点给所有区间排序
第二步:枚举所有区间。若当前区间没有点,那么就将点置于区间的右端点,以期许该点能覆盖往后更多的区间;若当前区间存在点(上次放置的点end的坐标大于区间左端点,这里由于区间右端点单增,end不可能超过区间右端点),跳过,枚举下一个区间。
- 这是典型贪心思想,每次选择局部最优,最后达到全局最优
C++ 代码(用pair来存区间)
【注意】按右端点排序,需要把区间右端点放在pair的第一关键字first上(pair按first排序)
按照y总那样用结构体存区间也可以,排序前记得重载一下小于号
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
const int N = 1e5+10;
int n;
PII q[N];
int main(){
cin>>n;
for(int i=0;i<n;i++){
int l,r;
cin>>l>>r;
q[i] = {r,l};
}
sort(q,q+n);
int res = 0, end = -1e9; //放置的点的数量、上次放置点的坐标
for(int i=0;i<n;i++){
int r = q[i].first, l = q[i].second;
if(l > end){
end = r;
res++;
}
}
cout<<res<<endl;
return 0;
}