题解 | 小sun的假期

看到大家都写区间合并，我这里写一种经典的区间差分做法。对于一段区间[l,r]，把l赋值成1，r+1赋值成-1,扔到一个桶里，然后排序，从前往后遍历，并用一个sum记录值，当sum=0的时候就表示当前没有被覆盖，记录一下前一个的状态和位置，当前一个是0,就可以更新答案，最后关注一下尾部的情况。

#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
int main(){
    int n,m;cin>>n>>m;
    using pii = pair<int,int>;
    vector<pii> v;
    for(int i=1;i<=m;i++){
        int l,r;cin>>l>>r;
        v.push_back({l,1});
        v.push_back({r+1,-1});
    }
    sort(v.begin(),v.end());
    int ans=0;
    int sum=0,pre=0,pos=1;
    for(int i=0;i<v.size();i++){
        int j=i;
        sum+=v[i].S;
        while(j+1<v.size()&&v[j+1].F==v[i].F){
            j++;
            sum+=v[j].S;
        }
        if(!pre){
            ans=max(ans,v[i].F-pos);
        }
        pre=sum,pos=v[i].F;
        i=j;
    }
    ans=max(n+1-pos,ans);
    cout<<ans<<"\n";
    return 0;
}