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

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N=10e5+5;
struct interval{
    long long  left;
    long long  right;
};
bool cmp(const interval& a, const interval& b) {
    return a.left < b.left;
}
int main(){
    long long n,m;
    cin>>n>>m;
    vector<interval> v(m);
    for(int i=0;i<m;i++){
        cin>>v[i].left>>v[i].right;
    }
    //将v根据left从小到大排序
    sort(v.begin(),v.end(),cmp);
    //贪心策略:
    //每次选择right最大的区间
    int count =0;//区间数量
    long long  place=0;//记录的已经选择的区间的right
    long long max_place=0;//此时的最大right
    bool is_duan=false;//判断是否有任一区间无法连接
    for(int i=0;i<m;i++){
        if(v[i].left<=place+1){
        	if(v[i].right==n){
                place=n;
        		count++;
        		break;
			} 
            max_place= max(max_place,v[i].right);
        }else{
            if(max_place==place){
                is_duan=true;
                break;
            }
            count++;
            place=max_place;
            i--;
        }
    }
    if(!is_duan)cout<<count;
    else cout<<"-1";
    return 0;
}