区间选点（贪心）

本文主要是介绍区间选点（贪心），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

说句题外话：今天2.27，立志在3.5号把基础课的贪心，dp看完，3.15号把数据结构和数学看完，然后看搜索！hhh，加油

给定 NN 个闭区间 [ai,bi][ai,bi]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。

输出选择的点的最小数量。

位于区间端点上的点也算作区间内。

输入格式

第一行包含整数 NN，表示区间数。

接下来 NN 行，每行包含两个整数 ai,biai,bi，表示一个区间的两个端点。

输出格式

输出一个整数，表示所需的点的最小数量。

数据范围

1≤N≤1051≤N≤105,
−109≤ai≤bi≤109−109≤ai≤bi≤109

输入样例：

3
-1 1
2 4
3 5

输出样例：

2
贪心的问题怎么说呢，就是先从眼前着手，不要想那么多，一步步走当前的最优解，最后走到全局的最优解（不一定）
其实说的严谨一点，需要证明，但贪心的问题证明起来很难

 最高赞题解里面有一个图十分的清晰易懂

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
struct range{
    int l,r;//左右端点 
}s[N];
int cmp(range x,range y)
{
    return x.r<y.r;
} 
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>s[i].l>>s[i].r;
    int t=0,ed=-2e9;
    sort(s+1,s+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        if(s[i].l>ed)//以一个区间为基准，如果这个区间的左端点大于上一个区间的右端点，就++，并且更新以备下一个区间继续用，
        //这个时候下一个区间的上一个就是本次的区间，所以刚刚更新的时候，就是更新这个区间 
        {
            t++;
            ed=s[i].r; 
        }
    } 
    cout<<t<<endl;
    return 0;
}

这篇关于区间选点（贪心）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！