题解 | 小sun的假期

最开始没看内存限制，写了朴素差分

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;

int main() {
    int n,m;cin >> n >> m;
    vector<int> nums(n+1);
    int l,r;
    for(int i = 1;i<=m;i++) {
        cin >> l >> r;
        nums[l] += -1;
        nums[r] += 1;
    }

    int ans = 0,number = 0,t = nums[1];
    for(int i = 2;i<=n;i++) {
        if(t == 0) {
            number++;
        } else {
            if(ans < number) ans = number;
            number = 0;
        }
        t += nums[i];
        //cout << t << ' ';
    }
    //cout << endl;
    if(ans < number) ans = number;
    cout << ans;
}

很明显，爆了

于是，优化了一下，维护了一个已经出现的最左的标点，当超出这个标点，就计算这两者的距离，取最大，最后特判一下结尾就好了

#include<bits/stdc++.h>
#include <vector>
#define endl '\n'
using namespace std;
using pii = pair<int,int>;

inline int max(int a,int b) { return (a>b)?a:b;}

int main() {
    int n,m;cin >> n >> m;
    vector<pii> nums;
    int l,r;
    for(int i = 0;i<m;i++) {
        cin >> l >> r;
        nums.emplace_back(pii(l,r));
    }
    sort(nums.begin(),nums.end());
    /*for(int i = 0;i<m;i++) {
        cout << nums[i].first << ' ';
    }
    cout << endl;*/
    int ans = nums[0].first-1;
    int left = nums[0].second;
    for(int i = 1;i<m;i++) {

        if(nums[i].first > left) {
            ans = max(ans,nums[i].first-left-1);
        }
        left = max(left,nums[i].second);
    }
    ans = max(ans,n-left);
    cout << ans;
    return 0;
}