核心:贪心,体现在每次选择点的时候,尽可能让他覆盖更多的区间,即一点多用
首先对所有区间按照右端点进行排序
从前往后枚举每个区间,将该区间的左端点和上次的保留的右端点(ed进行保存)进行比较:
如果该区间的左端点<ed:表示当前区间已经选择一个点了(即ed)
否则:需要选择一个新的点(即用当前区间的右端点更新ed)
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5;
struct Range{
int l, r;
bool operator< (const Range& w){
return r<w.r;
}
}range[N];
int main(){
int n;
cin>>n;
for(int i=0; i<n; i++) cin>>range[i].l>>range[i].r;
sort(range,range+n);
int res=0,ed=-2e9;
for(int i=0; i<n; i++){
if(range[i].l>ed){
res++;
ed=range[i].r;
}
}
printf("%d",res);
return 0;
}