题解 | 小sun的假期

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define all(a) a.begin(), a.end()
using vpii = vector<pair<int, int>>;

void solve() {
    int n, m;cin >> n >> m;
    vpii a(m);
    for (auto& [x, y] : a)cin >> x >> y;
    sort(all(a));
    int l = 1;
    int ans = 0;
    for (auto [x, y] : a) {
        ans = max(ans, x - l);
        l = max(l, y);
    }
    ans = max(ans, n - l);
    cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    for (int i = 1; i <= t; i++) {
        //cout << "----Test " << i << "----" << endl;
        solve();
    }
    return 0;
}

简单区间问题，要找没有覆盖的最大区间，排序后遍历即可，记录当前区间能覆盖的最右边，每次更新ans用当前左端点和上一个最右边的右端点更新，还要特判最后到n的区间