华华听月月唱歌

思路

这个是经典的区间合并问题

可以参考acwing 基础课模板的贪心部分

这里不多写题解了

ac 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int inf = 1e9;
typedef struct range{
    int l, r;
    bool operator<(const range &a) const{
        return this->l < a.l;
    }
} range;
vector<range> pairs;
int n;
int st, ed;
int m;
int rangeNum(){
    sort(pairs.begin(), pairs.end());
    int cnt = 0;
    for (int i = 0; i < n; ){
        int r = -inf;
        int j;
        for (j = i; j < n && pairs[j].l <= st; j++){
            r = max(r, pairs[j].r);
        }if (r < st) return -1;
        cnt++;
        if (ed <= r) return cnt;
        st = r + 1; i = j ;
    }
    return -1; // never reach there  , just for compile 
}
int main(){

    cin >> m;
    st = 1 , ed = m;
    cin >> n;
    for (int i = 0; i < n; i++){
        int a, b;
        cin >> a >> b;
        pairs.push_back({a, b});
    }
    cout << rangeNum() << endl;
    return 0;
}