分析
区间选点问题是一个经典的区间贪心问题,关键在于贪心的抉择
首先,对于一个区间来说,怎样选点会使得结果最好呢?对于一个没有规律的区间集合来说,不太明确,那么我们尝试把所有区间按照区间右端点的大小排序。
这样我们再来考虑这个问题,假设我们用一个end来表示当前遍历到的区间,如果我们假设end之前所有的区间取点都取好了,那么如何取下一个点呢?这下很明显,由于前面的点都取好了,那么我们只要考虑如何取点使得end之后的区间更容易包含整个点就可以了,那么就是取当前区间的右端点就可以了
之后就是对情况讨论,如果下一个区间包含end,也就是当前区间的右端点,那么就可以考虑下一个区间了,如果没有包含,也就是区间的左端点大于end,那么就要新加一个点,这个点同样,应该取下一个区间的右端点的位置,这样只要扫描一遍就可以了。
步骤
1.将所有点按照区间的右端点从小到大排序,如果右端点相同,就按照左端点从小到大排序,因为左端点越小,就越容易包含上一个点。
2.扫描一遍所有区间,每次对区间进行以上判断。
代码
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e5+5;
struct Range{
int l,r;
bool operator < (const Range& w)const{
return r<w.r||(r==w.r&&l<w.l);
}
}ranges[N];
int main(){
int n;
cin >> n;
for(int i=0;i<n;i++){
cin >> ranges[i].l >> ranges[i].r;
}
sort(ranges,ranges+n);
int ans=1;
int end=ranges[0].r;
for(int i=1;i<n;i++){
if(ranges[i].l>end){
ans++;
end=ranges[i].r;
}
}
cout << ans;
}