卢俊达

题目大意：

给出n个区间的上下界，求出最大连续区间的长度，几个连续区间之间的最大间隔。

思路：

把区间按照“上界由小到大，下界由大到小”的顺序排序并遍历，维护每个“连续区间”的上下界。判断一个区间是否与当前连续区间相连，只需要比较其下界与连续区间上界的大小关系即可。

若区间i不与当前连续区间相连，则新建一个连续区间（更新连续区间的上下界为区间i的上下界）。若区间i与当前连续区间相连，则（在区间i大于当前连续区间上界的情况下）更新连续区间的上界。

代码：

/*
ID: lujunda1
LANG: C++
PROG: milk2
*/
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdio>
#include<stdlib.h>
using namespace std;
//定义结构体，用于将每个区间的”上下界“封装起来，便于对区间进行排序。 
struct point
{
	int low;
	int high;
}range[5000];
//排序规则是：优先按照下界由小到大排序，若下界相同，则按照上界由小到大顺序排序。 
int cmp(const void* m,const void* n)
{
	if((*(point*)m).low==(*(point*)n).low)
		return (*(point*)m).high-(*(point*)n).high;
	return (*(point*)m).low-(*(point*)n).low;
} 
int main()
{
	freopen("milk2.in","r",stdin);
	freopen("milk2.out","w",stdout);
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		scanf("%d%d",&range[i].low,&range[i].high);
	qsort(range,n,sizeof(range[0]),cmp);
	//max表示最大连续时间，idle表示连续区间之间的最大间隔
	int max=range[0].high-range[0].low,idle=0;
	//temp_max表示当前区间i所在连续区间的长度
	//temp_low表示当前区间i所在连续区间的下界
	//temp_high表示当前区间i坐在连续区间的上界 
	for(int i=1,temp_max=max,temp_low=range[0].low,temp_high=range[0].high;i<n;i++)
	{
		//若区间i的下界不大于当前连续区间的上界 
		if(range[i].low<=temp_high)
			//更新当前连续区间的上界 
			temp_high=temp_high>range[i].high?temp_high:range[i].high;
		///若区间i的下界大于当前连续区间的上界
		else
		{
			//更新最大间隔 
			idle=idle>range[i].low-temp_high?idle:range[i].low-temp_high;
			//更新当前连续区间的上下界 
			temp_high=range[i].high;
			temp_low=range[i].low;
		}
		//更新当前连续区间的长度 
		temp_max=temp_high-temp_low;
		//更新连续区间长度最大值 
		max=max>temp_max?max:temp_max;
	}
	printf("%d %d\n",max,idle);
}