题目描述

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

输入格式
第一行包含两个整数s和t，表示给定线段区间的两个端点。
第二行包含整数N，表示给定区间数。
接下来N行，每行包含两个整数ai,bi，表示一个区间的两个端点。

输出格式
输出一个整数，表示所需最少区间数。
如果无解，则输出-1。

数据范围
1≤N≤105,
−109≤ai≤bi≤109,
−109≤s≤t≤109

样例

输入样例：
1 5
3
-1 3
2 4
3 5
输出样例：
2

贪心策略：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int st,ed;
int n;
struct stt{
    int l,r;
    bool operator < (const stt &x) const{
        return l< x.l;
    }
}stt[100005];
int main(){
    scanf("%d%d",&st,&ed);
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d%d",&stt[i].l,&stt[i].r);
    }
    sort(stt,stt+n);
    bool flag=false;
    int res=0;
    int r=-2e9;
    for(int i=0;i<n;i++){
        int j=i;
        r=-2e9;
//每次更新完右端点时都要重新把r赋值为很小很小的值，不然r在后面的区间右端点都小于上一次r的情况下会把上一次的r值带回来，
//这时r会一直等于st，且r<ed(无法覆盖)，会一直循环，直到i<n才结束，这就可能会造成超时  
        while(j<n&&stt[j].l<=st){
//找到所有左端点小于等于st的区间的最右端点 
            r=max(r,stt[j].r);
            j++;
        }
        if(r<st){
            res=-1;
         //flag=false;//忽略 
            break;
        }
        res++;
        if(r>=ed){
            flag=true;//只有这一个出口才算成功 
            break;
        }
        st=r;//更新st的值， 
        i=j-1;//一直在-1上纠结半天，发现自己还是c的基础没有打好，经过debug才发现这里i=j-1后，在执行for那一句话时i就会自己自动加1，又变成j了 
    }
    if(flag){//不可以直接输出res不用flag,例如给定区间[1,5],两个小区间[-1,2],[2,4], 
        printf("%d\n",res);
    }
    else{
        printf("-1\n");
    }
    return 0;
}