题解 | 小sun的假期

n<1e9,采用区间合并

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    if(m==0){
        cout<<n<<endl;
        return 0;
    }
    vector<pair<int,int>>a;
    for(int i=0;i<m;i++){
        int l,r;
        cin>>l>>r;
        a.push_back({l,r});
    }
    sort(a.begin(),a.end());
    vector<pair<int,int>>merged;
    int start=a[0].first,end=a[0].second;
    for(int i=1;i<m;i++){
        if(a[i].first<=end+1)end=max(end,a[i].second);
        else{
            merged.push_back({start,end});
            start=a[i].first;
            end=a[i].second;
        }
    }
    merged.push_back({start,end});
    int max_cnt=0,last_end=0;
    if(merged[0].first>1)max_cnt=max(max_cnt,merged[0].first-1);
    last_end=merged[0].second;
    for(int i=1;i<merged.size();i++){
        int start=last_end+1;
        int end=merged[i].first-1;
        if(start<=end){
            max_cnt=max(max_cnt,end-start+1);
        }
        last_end=max(last_end,merged[i].second);
    }
    if(last_end<n)max_cnt=max(max_cnt,n-last_end);
    cout<<max_cnt<<endl;
    return 0;
}