这道题的思路和方法很多，有用线段树的，1e6估计会超时，但是题目中的测试数据足够了，，，
我用的是不断修改和维护区间长度的方法，就是不停的修改，然后排序，最后就可以最大的就可以了。
/*
ID: wikioi_bai
PROG: milk2
LANG: C++
*/
# include<cstdio>
# include<iostream>
# include<algorithm>
using namespace std;
# define MAX 54321
int start[MAX];
int end[MAX];
int x[MAX];
int y[MAX];
int main(void)
{
freopen("milk2.in","r",stdin);
freopen("milk2.out","w",stdout);
int n;
while ( cin>>n )
{
for ( int i = 0;i < n;i++ )
cin>>start[i]>>end[i];
sort( start,start+n );
sort( end,end+n );
y[0] = end[0] - start[0];
for ( int i = 1;i <= n;i++ )
{
if ( start[i] <= end[i-1] )
{
start[i] = start[i-1];
}
y[i] = end[i] - start[i];
}
for ( int i = 1;i < n;i++ )
{
if ( start[i] > end[i-1] )
{
x[i-1] = start[i] - end[i-1];
}
}
sort(x,x+n);
sort(y,y+n);
cout<<y[n-1]<<" ";
cout<<x[n-1]<<endl;
}
return 0;
}
方法二：
另外附带上哈希解法：
1e6的范围，开一个布尔数组完全可以，有人为TRUE，无人为FALSE，注意边界即可。最后线性扫描即可。
时间复杂度，应该是O(n),n为最后结束的时间。
缺点就是……比较慢
和我的方法比较像，但我做了些优化
预处理：
建立一个数组a。
读入，若为起点将a[i]加1，若为终点将a[i]减1。
（这时顺便找出总的起点与终点）；
算法开始：
将数组扫一遍（注意从总的起点扫到总的终点），这时将x（初始为0）加上a[i]。
若遇到x由0变1，或由1变0，
将这个点计入数组ans[]。
然后再将ans扫描一遍，大家可能都想到了：
若i为奇数，ans[i+1]-ans[i] 应该是有人的时间间隔；
若i为偶数，反之。
这个算法是O(n)，实际效果不错，但我也不知道应该叫什么。
回楼上的话，这种方法可以称之为是差分。见noip2012提高组 借教室。具体指有一列数字a，
再找来一个数组s记录相邻数字之差，这样每个数字a[i]都是s[1]+s[2]+...+s[i-1]。对于一
段数字的加减法就可以通过将这一段开头的差加上相应的数字，再把这一段结尾的数字减去相
应的数值即可。很巧妙的方法。
#include <stdio.h>
#include <memory.h>
int main(void)
{
int n,i,a,b,j,m1=1000000,m2=0,max[2]={0,0};
char hash[1000000];
//freopen("milk2.in","r",stdin);freopen("milk2.out","w",stdout);
memset(hash,0,sizeof hash);
scanf("%d",&n);
for (i=0;i<n;++i)
{
scanf("%d%d",&a,&b);
--b;
if (a<m1) m1=a;
if (b>m2) m2=b;
for (j=a;j<=b;++j) hash[j]=1;
}
for (i=m1;i<m2;i+=j)
{
for (j=0;hash[i+j]==hash[i];++j);
if (j>max[hash[i]]) max[hash[i]]=j;
}
printf("%d %d\n",max[1],max[0]);
fclose(stdin);fclose(stdout);
return 0;
}
描述
三个农民每天清晨5点起床，然后去牛棚给3头牛挤奶。第一个农民在300秒(从5点开始计时)给他的牛挤奶，一直到1000秒。第二个农民在700秒开始，在 1200秒结束。第三个农民在1500秒开始2100秒结束。期间最长的至少有一个农民在挤奶的连续时间为900秒(从300秒到1200秒)，而最长的无人挤奶的连续时间(从挤奶开始一直到挤奶结束)为300秒(从1200秒到1500秒)。
你的任务是编一个程序，读入一个有N个农民(1 <= N <= 5000)挤N头牛的工作时间列表，计算以下两点(均以秒为单位):
- 最长至少有一人在挤奶的时间段。
- 最长的无人挤奶的时间段。（从有人挤奶开始算起）
[编辑]格式
PROGRAM NAME: milk2
INPUT FORMAT:
(file milk2.in)
- 第1行:一个整数N。
- 第2至第N+1行:每行两个小于1000000的非负整数，表示一个农民的开始时刻与结束时刻。
OUTPUT FORMAT:
(file milk2.out)
一行，两个整数，即题目所要求的两个答案。
[编辑]SAMPLE
INPUT
3 300 1000 700 1200 1500 2100
[编辑]SAMPLE
OUTPUT
900 300