P1204 [USACO1.2]挤牛奶Milking Cows
分析：初始化变量头和尾为第一个农民的开始时间和结束时间，max1,max2为最大重叠长度和最大不重叠长度每处理一个农民，相当于处理一条线段，首先先对每一条线段的初始端排序，接着从第二条开始处理，如果下一条线段起点小于当前尾部，说明可能有覆盖取max1=max(当前的尾,这条线段的末端），反之则开始计算最大不重叠长度max2=max(max2,当前线段起点-当前尾部）并更新头尾（分别赋值为当前线段的起点和终点）（讲的应该够详细了...
代码语言：javascript复制#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<iomanip>
using namespace std;
struct node
{
int begin,end;
}p[5005];
bool cmp(node a,node b)
{
return a.begin<b.begin;
}
int n,max1,max2,head,tail;
int main()
{
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i )
{
cin>>p[i].begin>>p[i].end;
}
sort(p 1,p 1 n,cmp);
head=p[1].begin,tail=p[1].end;
for(int i=2;i<=n;i )
{
if(p[i].begin<=tail)tail=max(tail,p[i].end);
else
{
max1=max(max1,tail-head);
max2=max(max2,p[i].begin-tail);
head=p[i].begin,tail=p[i].end;
}
}
max1=max(max1,tail-head);
cout<<max1<<" "<<max2;
return 0;
}
