一看就感觉很贪心
考虑左端点最大的区间 $p$ 和右端点最小的区间 $q$
如果 $p,q$ 属于同一个集合（设为 $S$，另一个集合设为 $T$），那么其他的区间不管是不是在 $S$ 都不会影响 $S$ 的交集大小
那么为了最优显然我们只要留一个最长的区间给 $T$ ，然后其他全给 $S$
代码实现的时候枚举不属于 ${p,q}$ 的最长区间时也可以考虑 $p,q$ 的区间长度，并不影响答案
然后考虑 $p,q$ 不属于同一个集合的情况，不妨设 $p$ 在 $S$ ， $q$ 在 $T$
设第 $i$ 个区间的左端点为 $L[i]$，右端点为 $R[i]$
那么答案为 $max(0,min_{i \in S} (R[i]) -L[p])+max(0,R[q]-max_{i \in T}(L[i]))$
现在问题就是求这个式子的最大值
把区间按 $L$ 排序，枚举 $k$ ，把前 $k$ 名的区间给 $T$ ，剩下给 $S$
这样即可保证枚举到式子 $max(0,R[q]-max_{i \in T}(L[i]))$ 中的 $max_{i \in T}(L[i])$ 的所有情况
具体维护的话就预处理前缀后缀 $min,max$ 即可
代码实现的时候同样可以不用强制 $p,q$ 不属于同一个集合，因为不影响答案
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<vector> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘) f=-1; ch=getchar(); } while(ch>=‘0‘&&ch<=‘9‘) { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=2e5+7,INF=1e9; int n,ans; struct dat { int l,r; dat (int _l=0,int _r=0) { l=_l,r=_r; } inline bool operator < (const dat &tmp) const { return l!=tmp.l ? l<tmp.l : r<tmp.r; } }d[N]; int lx[N],rx[N],ly[N],ry[N]; int main() { n=read(); for(int i=1;i<=n;i++) d[i].l=read(),d[i].r=read(); sort(d+1,d+n+1); lx[1]=d[1].l,rx[1]=d[1].r; for(int i=2;i<=n;i++) { lx[i]=max(lx[i-1],d[i].l); rx[i]=min(rx[i-1],d[i].r); } ly[n]=d[n].l; ry[n]=d[n].r; for(int i=n-1;i>=1;i--) { ly[i]=max(ly[i+1],d[i].l); ry[i]=min(ry[i+1],d[i].r); } for(int i=1;i<n;i++) ans=max(ans,max(0,rx[i]-lx[i]+1)+max(0,ry[i+1]-ly[i+1]+1)); for(int i=1;i<=n;i++) ans=max(ans,d[i].r-d[i].l+1+max(0 , min(ry[i+1],rx[i-1])-max(ly[i+1],lx[i-1])+1 )); printf("%d\n",ans); return 0; }
AtCoder Grand Contest 040 B - Two Contests
原文：https://www.cnblogs.com/LLTYYC/p/11792428.html