2300 - 1-2-1 Milking Cows 挤牛奶
三个农民每天清晨5点起床，然后去牛棚给3头牛挤奶。第一个农民在300秒(从5点开始计时)给他的牛挤奶，一直到1000秒。第二个农民在700秒开始，在 1200秒结束。第三个农民在1500秒开始2100秒结束。期间最长的至少有一个农民在挤奶的连续时间为900秒(从300秒到1200秒)，而最长的无人挤奶的连续时间(从挤奶开始一直到挤奶结束)为300秒(从1200秒到1500秒)。
你的任务是编一个程序，读入一个有N个农民(1 <= N <= 5000)挤N头牛的工作时间列表，计算以下两点(均以秒为单位):
- 最长至少有一人在挤奶的时间段。
- 最长的无人挤奶的时间段。（从有人挤奶开始算起）
题目输入
一个整数N。
每行两个小于1000000的非负整数，表示一个农民的开始时刻与结束时刻。
题目输出
一行，两个整数，即题目所要求的两个答案。
输入/输出样例
题目输入
3 300 1000 700 1200 1500 2100
题目输出
900 300
C++解答
#include <iostream> #include <stdio.h> #include <algorithm> using namespace std; struct Line{ int startPoint; int endPoint; }; bool Cmpare(Line &lineA,Line &lineB){ return lineA.startPoint <lineB.startPoint; } int main(void){ int n = 0; // printf("请输入农民数量N:"); scanf("%d",&n); Line line[n]; for(int i = 0;i<n;i++){ // printf("%d\n",i); int startTime ,endTime = 0; scanf("%d%d",&line[i].startPoint,&line[i].endPoint); } // printf("************\n"); sort(line,line+n,Cmpare); // for(int i = 0;i<n;i++){ // printf("%d %d\n",line[i].startPoint,line[i].endPoint); // } Line lineMerge[n]; lineMerge[0].startPoint = line[0].startPoint; lineMerge[0].endPoint = line[0].endPoint; int lineNum = 1; for(int i = 1;i<n;i++){ if(line[i].startPoint <= lineMerge[lineNum-1].endPoint){ //如果下一段的起始点在上一段终点前，说明有可能可以合并，作判断 if(line[i].endPoint >= lineMerge[lineNum-1].endPoint){ lineMerge[lineNum-1].endPoint = line[i].endPoint; } }else{ // 如果下一段的起始点超过上一段终点，则计算新的线段 lineMerge[lineNum].startPoint = line[i].startPoint; lineMerge[lineNum].endPoint = line[i].endPoint; lineNum = lineNum +1; } } // for(int i = 0;i<lineNum;i++){ // printf("%d %d\n",lineMerge[i].startPoint,lineMerge[i].endPoint); // } int maxTime = lineMerge[0].endPoint - lineMerge[0].startPoint; int minTime = 0; for(int i = 1;i<lineNum;i++){ if(lineMerge[i].endPoint - lineMerge[i].startPoint>maxTime){ maxTime = lineMerge[i].endPoint - lineMerge[i].startPoint; } if(lineMerge[i].startPoint - lineMerge[i-1].endPoint>minTime){ minTime = lineMerge[i].startPoint - lineMerge[i-1].endPoint; } } printf("%d %d",maxTime,minTime); }