Description
三个农民每天清晨5点起床，然后去牛棚给3头牛挤奶。第一个农民在300时刻(从5点开始计时，秒为单位)给他的牛挤奶，一直到1000时刻。第二个农民在700时刻开始，在 1200时刻结束。第三个农民在1500时刻开始2100时刻结束。期间最长的至少有一个农民在挤奶的连续时间为900秒(从300时刻到1200时刻)，而最长的无人挤奶的连续时间(从挤奶开始一直到挤奶结束)为300秒(从1200时刻到1500时刻)。
你的任务是编一个程序，读入一个有N个农民(1 <= N <= 5000)挤N头牛的工作时间列表，计算以下两点(均以秒为单位):
• 最长至少有一人在挤奶的时间段。
• 最长的无人挤奶的时间段。
Input
Line 1: 一个整数N。
Lines 2…N+1: 每行两个小于1000000的非负整数，表示一个农民的开始时刻与结束时刻。
Output
一行，两个整数，即题目所要求的两个答案。
Sample Input
3
300 1000
700 1200
1500 2100
Sample Output
900 300
.
.
.
.
.
.
分析
离散化(我打的真的是离散吗？)
每一段时间都可以看成一条线段
将开头和结尾映射到数轴上
在数轴上从左到右扫描
对于一个点，如果它在某一条线段上，则累加
(注意，对于时间的间隔，它只可能存在于两点之间)
.
.
.
.
.
程序：(代码丑陋，请别介意)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,x1[6000],y1[6000],x[10001];
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
scanf("%d%d",&x1[i],&y1[i]);
x[i*2-1]=x1[i];
x[i*2]=y1[i];
}
sort(x+1,x+2*n+1);
long long ans1=0,ans2=0,fa1=0,fa2=0;
for (int i=2;i<=2*n;i++)
{
int bz=0;
for (int j=1;j<=n;j++)
if (x[i]<=y1[j]&&x[i-1]>=x1[j])
{
bz=1;
fa1+=x[i]-x[i-1];
break;
}
if (bz==1&&fa1>ans1) ans1=fa1;
if (bz==0)
{
fa1=0;
fa2=x[i]-x[i-1];
if (fa2>ans2) ans2=fa2;
}
}
cout<<ans1<<' '<<ans2;
return 0;
}