1 solutions

  • 0
    @ 2025-7-2 11:57:49
    #include<bits/stdc++.h>
    using namespace std;
    const int N=1e5+10;
    typedef pair<int,int> PII;
    #define l first
    #define r second
    PII q[N];
    int main()
    {
        int st,ed;
        cin>>st>>ed;
        int n;
        cin>>n;
        for(int i=0;i<n;i++)
        {
            int l,r;
            cin>>l>>r;
            q[i]={l,r};
        }
        sort(q,q+n);
        int res=0;
        bool su=false;
        for(int i=0;i<n;i++)
        {
            int r=-2e9;
            int j=i;
            while(j<n&&q[j].l<=st)
            {
                r=max(r,q[j].r);
                j++;
            }
            j--; //走到小于等于起点的地方
            if(r<st) break; //最长的右端点也小于起点
            res++;
            if(r>=ed) //已经完全覆盖
            {
                su=true;
                break;
            }
            st=r; //更新当前选择点以后可以覆盖到的最远的点
            i=j;
        }
        if(su) cout<<res;
        else cout<<-1;
        return 0;
    }
    

    Information

    ID
    250
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    5
    Tags
    # Submissions
    11
    Accepted
    4
    Uploaded By