题目描述

区间选点

区间问题：
（1）区间排序：按每个区间的右端点大小排序
（2）从前往后依次枚举每个区间
若当前区间中已经包含这个点则继续枚举
若当前区间不包含，则选择这个区间的右端点

贪心问题：每次选择最好的情况（局部最优解）

ans:方案的最小值
cnt:一种方案（相互之间没有交集的区间个数）所以至少需要cnt个点
选择的方案点数一定大于等于cnt
通过证明ans>=cnt&&ans<=cnt得到ans==cnt

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=100010;
int n;
struct Range
{
    int l,r;  //左右两个端点
    bool operator<(const Range &W)const
    {
        return r<W.r;    //按右端点排序
    }

}range[N];

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int l,r;
        cin>>l>>r;
        range[i]={l,r};
    }

    sort(range,range+n);  //排序

    int res=0;//当前选的点的数量
    int ed=-2e9;//上一个点的下标（没有选的时候为负无穷）
    for(int i=0;i<n;i++)
    {
        if(range[i].l>ed)   //即已经选的点没有包含在这个区间里
        {
            res++;        //再选一个新的点，点的数量++
            ed=range[i].r;   //新的点选择该区间的右端点
        }
    }
    cout<<res<<endl;  //输出点的数量
    return 0;
}