题目描述

给定N个闭区间[ai,bi]以及一个线段区间[s,t]，请你选择尽量少的区间，将指定线段区间完全覆盖。
输出最少区间数，如果无法完全覆盖则输出-1。

样例

1 5
3
-1 3
2 4
3 5

2

算法分析

这是一道经典的贪心，策略大概是这样的
1.将所有左端点从小到大排序
2.从左往右枚举所有区间，在所有可以覆盖start的区间中，选出右端点最远的区间
3.将start更新为右端点的最大值

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e6+10;
int n; 
struct Range{
    int l,r;
    bool operator< (const Range &w) const{
        return l<w.l;
    }
}range[N];

int main(){
    int st;
    int ed;
    cin>>st>>ed;
    scanf("%d",&n);

    for(int i=0;i<n;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        range[i]={l,r};
    }
    int res=0;
    bool success=false;
    sort(range,range+n);
    for(int i=0;i<n;i++){
        int j=i,r=-2e9;
        while(j<n&&range[j].l<=st){
            r=max(r,range[j].r);
            j++;
        }
        if(r<st){
            res=-1;
            break;
        }
        res++;
        if(r>=ed){
            success=true;
            break;
        }
        st=r;
        i=j-1;
    }
    if(!success) res=-1;
    cout<<res<<endl;
    return 0;
}