区间选点
题目 区间选点
思路分析
数轴上有一些区间，在数轴上选取几个点，要求每个区间上最少有一个点
其实是一个区间交集的问题 区间问题根据前面区间合并的经验 肯定是要先排序的 然后对于交集问题 贪心的想法是 靠前的区间要与后面的区间有交集 肯定是在右半部分 若右半都与后面一个区间没交集 左边就更不要说了 再贪一点其实就是只要看每个区间的右端点了呗
1、将区间按右端点排序
2、遍历区间，end值初始化为无穷小
如果本次区间不能覆盖掉上次区间的右端点，ed < range[i].l，说明需要选择一个新的点，res ++ ; ed = range[i].r;
如果本次区间可以覆盖掉上次区间的右端点，则进行下一轮循环
3、输出所选点的个数
证明：
假设最优解为 ans 个点，贪心算法求出的为 cnt 个点。 只需要证明 ans == cnt 即可。
因为 ans 是最优解，所以 ans <= cnt。
贪心算法求出的结果为 cnt,每次让选取点数+1的区间一定不相交。共计cnt个这样的区间。，为了覆盖这cnt个区间, 至少需要cnt个点。所以ans
= cnt。
综上： cnt == ans
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n;
struct Range{
int l,r;
bool operator< (const Range &w)const{
return r<w.r;
}
}ranges[N];
int main()
{
cin>>n;
for(int i=0;i<n;i++)
cin>>ranges[i].l>>ranges[i].r;
sort(ranges,ranges+n);
int res=0;
int ed=-2e9;
for(int i=0;i<n;i++){
if(ranges[i].l>ed){
res++;
ed=ranges[i].r;
}
}
cout<<res;
return 0;
}
💬 评论