题解 | #华华听月月唱歌#

#include<bits/stdc++.h>
#include<iostream>
using namespace std;
struct fragm
{
    int l;
    int r;
}fm[100010];
bool comp(fragm a,fragm b)
{
    return a.r>b.r;
}
int N,M;
int main()
{
    cin>>N>>M;
    for(int i=0;i<M;i++)
    {
        cin>>fm[i].l>>fm[i].r;
    }
    sort(fm,fm+M,comp);
    int right=0;
    int cnt=0;
    int x=M;
    int flag = 1;
    if(fm[0].r<N)
    {
        cout<<-1;
        return 0;
    }
    while(flag)
    {
        flag = 0;//1表示找到,0表示没找到
        for(int i=0;i<x;i++)
        {
            if(fm[i].l<=right+1)
            {
                right = fm[i].r;
                cnt++;
                x = i;
                flag = 1;
                if(right==N)
                {
                    cout<<cnt;   
                    return 0;
                }
                break;
            }
        }
    }
    cout<<-1;
    return 0;
}

本题实质是一道基础的贪心题，但难在要去证明贪心策略的正确性。 本题贪心策略就是每次选右端点靠右的片段,因为在已经选择一些片段的前提下，如果选择右端点靠左的片段能成功，那么这个片段的选择对于右端点靠右的片段一定也能成功（甚至片段能更少）；而右端点靠右的片段能成功的方法对于右端点靠左的片段不一定能成功，这样看当然选择右端点靠右的片段。

同时注意本题的“做不到”是指找不到下一步可衔接的片段了（左端点小于等于目前整体右端点+1）。