区间选点

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

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

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

输入格式
第一行包含整数 N，表示区间数。

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

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

数据范围
1≤N≤10^5,
−10^9≤ai≤bi≤10^9
输入样例：
3
-1 1
2 4
3 5
输出样例：
2

操作：

1.将每个区间按照右端点从小到大进行排序
2.从前往后枚举区间，end值初始化为无穷小
如果当前区间中已经包含点，则直接进入下一轮循环；否则，选择当前区间的右端点

证明：

1.ans<=cnt
目标值（最优解，即所有可行方案的最小值）是ans ;当前选择的点数(按照上方的操作选择)是cnt

2.ans>=cnt
由于我们选择的点都是每个区间的右端点，所以当前选择的点数cnt,也就是cnt个区间。
这些区间从左到右依次排好，并且相邻两个区间之间没有交集。如果要把cnt个
覆盖掉的话，我们至少需要cnt个点，所以我们选的点数可以大于（或等于）cnt

综上,ans=cnt，贪心策略是正确的

应用 ： 雷达设备

#include <iostream>
#include <algorithm>
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()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d%d", &range[i].l, &range[i].r);

    sort(range, range + n);

    int res = 0, ed = -2e9;//ed表示所选的上一个点的下标，由于最开始，还没有选，所以赋值负无穷
    for (int i = 0; i < n; i ++ )
        if (ed < range[i].l)//区间之间没有交集
        {
            res ++ ;
            ed = range[i].r;
        }

    printf("%d\n", res);

    return 0;
}

最大不相交区间数量

给定 N 个闭区间 [ai,bi]，请你在数轴上选择若干区间，使得选中的区间之间互不相交（包括端点）。

输出可选取区间的最大数量。

输入格式
第一行包含整数 N，表示区间数。

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

输出格式
输出一个整数，表示可选取区间的最大数量。

数据范围
1≤N≤10^5,
−10^9≤ai≤bi≤10^9
输入样例：
3
-1 1
2 4
3 5
输出样例：
2

应用  ： 在没有冲突的情况下选择课程，使时间最少


我们发现这道题与上道题其实一模一样（代码也一模一样），上题已经提到选的点是每个区间的右端点，选的点数cnt==没有交集的区间数

区间分组

给定 N 个闭区间 [ai,bi]，请你将这些区间分成若干组，使得每组内部的区间两两之间（包括端点）没有交集，并使得组数尽可能小。

输出最小组数。

输入格式
第一行包含整数 N，表示区间数。

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

输出格式
输出一个整数，表示最小组数。

数据范围
1≤N≤10^5,
−10^9≤ai≤bi≤10^9
输入样例：
3
-1 1
2 4
3 5
输出样例：
2

操作：

1.将所有区间按照左端点从小到大排序
2.从前往后处理每个区间：
判断能否将其放到某个现有的组中：找到这个组中右端点最靠右的。判断下一组区间左端点最靠左的是否与其有交集
1.如果不存在这样的组(即l[i]<=max_r(有交集))，则开新租，然后将其放进去
2.如果存在这样的组(l[i]>=max_r(没有交集))，将其放进去，并更新当前的max_r

综上，我们排序后，找是否存在一个组使得max_r（所有组中的max_r的最小值）>=l[i]或max_r=l[i],而这个max_r可以用小根堆来维护

应用 ：畜栏预定

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 100010;

int n;
struct Range{
    int l, r;

    bool operator< (const Range &W) const{
        return l < W.l;//按照左端点进行排序
    }
}range[N];

int main(){
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) cin >> range[i].l >> range[i].r;

    sort(range, range + n);

    priority_queue<int, vector<int>, greater<int>> heap;//我们的小根堆始终保证所有组中的最小的右端点为根节点
    //用堆来存储组的右端点
    for (int i = 0; i < n; i ++ ){
        auto t = range[i];

        if (heap.empty() || heap.top()>=t.l)
        //如果当前队列为空，或者区间的端点小于小根堆的根（当前组的最小右端点）
            heap.push(t.r);
            //自己单开一个新组
        else{
            heap.pop();
    //如果大于组当中的最小右端点，说明它至少肯定和这个组没有交集，没有交集那就把它归到这一组里
            heap.push(t.r);
        //既然大于我们小根堆的根，也就说明把它该归到小根堆根所代表的这一组，根就失去了作用
        }
//我们将跟去掉，用新的t.r来放入小根堆里，小根堆替我们自动找到所有组当中为所有组的最小右端点，并作为新根
    }

    cout << heap.size() << endl;//我们就是用size来表示的组的

    return 0;
}

区间覆盖

给定 N 个闭区间 [ai,bi] 以及一个线段区间 [s,t]，请你选择尽量少的区间，将指定线段区间完全覆盖。

输出最少区间数，如果无法完全覆盖则输出 −1。

输入格式
第一行包含两个整数 s 和 t，表示给定线段区间的两个端点。

第二行包含整数 N，表示给定区间数。

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

输出格式
输出一个整数，表示所需最少区间数。

如果无解，则输出 −1。

数据范围
1≤N≤10^5,
−10^9≤ai≤bi≤10^9,
−10^9≤s≤t≤10^9
输入样例：
1 5
3
-1 3
2 4
3 5
输出样例：
2

操作：

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10,INF=0x3f3f3f3f;
int st,ed,n;
struct Range{
    int l,r;
    bool operator < (const Range &W) const{
        return l< W.l;
    }
}range[N];

int main(){

    scanf("%d%d",&st,&ed);//目标区间
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        int a,b;
        scanf("%d%d",&a,&b);

        range[i]={a,b};
    }

    sort(range,range+n);

    bool flag=false;   //判断是否成功，初值为失败
    int res=0;

    for(int i=0;i<n;i++){
        int j=i,r=-INF; //r表示当前的最大值
        //如果每次不把r更新为-2e9的话，st和r相等，可能不会出现r<st的情况，如果无法覆盖的话，就会一直循环
        while(j<n&&range[j].l<=st){   //双指针算法来更新左端点小于st的线段中，能够到大的最远位置
            r=max(r,range[j].r);
            j++;
        }

        if(r<st){     //当前右端点的最远位置不能到达下一线段的左端点，一定不能覆盖
            res=-1;
            break;
        }

        res++;
        if(r>=ed){
            flag=true;  //只有从这个出口出去才被视作成功覆盖
            break;
        }

        st=r;    //更新下一次的st，i
        i=j-1;    //因为满足条件后j++

    }
    if(flag)  cout<<res<<endl;
    else cout<<-1<<endl;
}