这题方法很多，我首先想到的就是题解的第一种方法。以后的方法有待慢慢体会学习，此文将不断更新中……
一、离散化
（其实就是进行了优化的搜索而已）
按照开始时间升序排序，然后从左到右扫一遍，复杂度是O(nlogn+n)的（排序+扫一遍，用堆、合并、快排都可以）。
所谓从左到右扫一遍，就是记录一个当前区间，[tmp_begin , tmp_end]
如果下一组数据的begin比tmp_end的小（或相等），则是连接起来的，检查这组数据的end，取max{end , tmp_end}。
如果下一组数据的begin比tmp_end的大，则是相互断开的，整理本区间。maxn1取max{tmp_end - tmp_begin , maxn1}。maxn2取max{begin - tmp_end , maxn2} 。
具体代码：
/* ID: Tony PROG: milk2 LANG: C++ */ #include<cstdio> #include<algorithm> using namespace std; #define N 5000+10 typedef struct{ int s,e; }Fa; bool cmp(Fa a,Fa b) { return a.s<b.s; } int main() { freopen("milk2.in","r",stdin); freopen("milk2.out","w",stdout); int num,cont; Fa cur,fa[N]; scanf("%d",&num); for(int i=0;i<num;i++) scanf("%d%d",&fa[i].s,&fa[i].e); sort(fa,fa+num,cmp); int maxn1=0,maxn2=0; cur=fa[0]; for(int i=1;i<num;i++) { if(fa[i].s>cur.e) { cont=fa[i].s-cur.e; if(cont>maxn2) maxn2=cont; cont=cur.e-cur.s; if(cont>maxn1) maxn1=cont; cur=fa[i]; } else { if(fa[i].e>cur.e) cur.e=fa[i].e; } } cont=cur.e-cur.s; if(cont>maxn1) maxn1=cont; printf("%d %d/n",maxn1,maxn2); return 0; }
