区间覆盖问题（详细注释）

//算法思想：1.将所有区间按照左端点从小到大进行排序。
//2.从前往后枚举每个区间，在所有能覆盖start的区间中，选择右端点的最大区间，然后将start更新成右端点
//的最大值。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>

using namespace std;

const int N=100010;

typedef pair<int ,int> PII;

PII num[N];
int st,ed;

int main(){

    cin>>st>>ed;//输入目标区间的起点和终点
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        num[i]={a,b}; //用pair来存储方便排序
    }

    sort(num,num+n);//按照左端点的大小从小到大排序

    bool success=false;//用于判断是否到达右端点
    int res=0;//表示所需区间的个数，才能覆盖目标区间
    for(int i=0;i<n;i++){
        //遍历每一个区间
        int j=i, r=-2e9;
        //每一次都寻找覆盖st端点的区间的右端点的最大值
        while(j<n && num[j].first<=st){
            r=max(r,num[j].second);
            j++;
        }

        //如果当前所有的区间都没能覆盖st，则输出-1
        if(r<st){
            res=-1;
            break;
        }

        //每次找到覆盖st端点的区间的右端点的最大值之后，区间个数加1
        res++;
        if(r>=ed){//如果已经覆盖目标区间
            success=true;
            break;
        }
        st=r;  //更新st
        i=j-1;//更新i为的是避免重复遍历，j走过的i就没必要再走一次。
        //之所等于j-1是因为for循环里有i++
    }

    if(!success) res=-1;

    cout<<res;

    return 0;
}