简化题意：求至少有一条线段覆盖的最大区间和没有线段覆盖的最大区间（注意题目是左闭右开区间（好像左开右闭也可以？））
第一反应：线段树（wu)
这道题做法好像很多的样子啊。
虽然以这道题“渺小”的数据范围来说，不需要特别优秀的解法。
法一
比较直观的一个方法。
对所有的线段按照左端点从小到大进行排序。
扫一遍，把所有重叠的线段合并起来。
再扫一遍，统计两种答案。
法二
算是上面的那个方法的变形吧。
对所有的线段按照左端点从小到大进行排序。
设置两个变量$s$,$t$，表示当前可以被连续覆盖的区间的起点和终点。
如果能够接得上，即$f[i].l<=t$，那么更新右端点：$t=max(t,f[i].t)$
如果接不上，就更新答案：
有线段覆盖的区间$ans1=max(ans1,t-s)$
没有线段覆盖的区间，就是当前这一条线段接不上的空隙：$ans2=max(ans2,f[i].l-t)$
并且对当前可以被连续覆盖的区间进行更新：$s=f[i].l,t=f[i].r$
注意我们更新答案是在不能继续接上的时候更新，但是最后一段可以被连续覆盖的区间没有这个“契机”去统计答案，所以要在循环结束的时候单独用最后一段$s$,$t$更新一遍答案。
1 /* 2 ID:Starry21 3 LANG:C++ 4 TASK:milk2 5 */ 6 #include<iostream> 7 #include<string> 8 #include<cstdio> 9 #include<cstring> 10 #include<map> 11 #include<algorithm> 12 using namespace std; 13 #define N 5005 14 int n; 15 struct node{ 16 int l,r; 17 }f[N]; 18 bool cmp(node p,node q) 19 { 20 return p.l<q.l; 21 } 22 int main() 23 { 24 //freopen("milk2.in","r",stdin); 25 //freopen("milk2.out","w",stdout); 26 scanf("%d",&n); 27 for(int i=1;i<=n;i++) 28 scanf("%d %d",&f[i].l,&f[i].r); 29 sort(f+1,f+n+1,cmp); 30 int s=f[1].l,t=f[1].r,ans1=0,ans2=0; 31 for(int i=2;i<=n;i++) 32 { 33 if(f[i].l<=t) t=max(t,f[i].r); 34 else 35 { 36 ans1=max(ans1,t-s); 37 ans2=max(ans2,f[i].l-t); 38 s=f[i].l,t=f[i].r; 39 } 40 } 41 ans1=max(ans1,t-s); 42 printf("%d %d ",ans1,ans2); 43 return 0; 44 }
法三
受到树状数组的思想的影响，可以采用差分前缀和的方法。
每条线段的起点$+1$,终点$-1$。
前缀和大于$0$表示这个位置被覆盖了。
（发现它躺在草稿箱里，不造为啥没发 可能是法三代码没贴上来？不管了