题解 | #想要更多的0#

思路：假设已将区间 $[0,0][0,\; 0]$ 恢复,设 $l,rl,\; r$ 为已恢复区间左右端点，将所有区间以左端点为第一关键字，右端点为第二关键字，升序排列
每次循环，从后面区间中找到一个 $\mathrm{区}\mathrm{间}\mathrm{左}\mathrm{端}\mathrm{点}\le r+1区间左端点\backslash le\; r+1$ 并且区间右端点最大的区间，并计入总数，如果没找到这样的区间，就无法完成恢复
$CodeCode$

#include <algorithm>
#include <array>
#include <iostream>
#define rep(i, a, n) for(int i=(a); i<=(n); i++)
using namespace std;
using ar2 = array<int, 2>;
const int N = 1e5+10;
int n, m;
ar2 a[N];
int solve()
{
    cin >> n >> m;
    rep(i, 1, m) cin >> a[i][0] >> a[i][1];//读入所有区间（从下标1开始读）
    sort(a + 1, a + m + 1, [](ar2 a, ar2 b){
        if(a[0] == b[0]) return a[1] < b[1];
        return a[0] < b[0];
    });//区间排序，左端点为第一关键字，右端点为第二关键字，小的在前面
    int ans = 0;
    int l = 0, r = 0, k = 1;//l，r为已经恢复的区间的左右端点，k为当前要扫描的区间
    while(1)
    {
        int tr = r;//tr表示已经恢复的区间的右端点
        for(int tk=k;k <= m;k ++)
        {
            if(a[k][0] <= tr + 1) r = max(r, a[k][1]);
            else if(tk == k) return -1;
            else break;
        }//从后面的区间中找出能与已恢复的区间对接，并且右端点最大的区间
        ans ++;//将该区间计入总数
        if(k > m || r >= n) break;//如果已经遍历完毕或者当前符合条件的区间右端点为n，退出循环
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // int t; cin >> t;
    // while(t--)
    cout << solve();

    return 0;
}