题目描述
1
输入格式
64
输出格式
【问题描述】
三个农民每天清晨5点起床，然后去牛棚给3头牛挤奶。第一个农民在300秒(从5点开始计时)给他的牛挤奶，一直到1000秒。第二个农民在700秒开始，在 1200秒结束。第三个农民在1500秒开始2100秒结束。期间最长的至少有一个农民在挤奶的连续时间为900秒(从300秒到1200秒)，而最长的 无人挤奶的连续时间(从挤奶开始一直到挤奶结束)为300秒(从1200秒到1500秒)。
你的任务是编一个程序，读入一个有N个农民(1 <= N <= 5000)挤N头牛的工作时间列表，计算以下两点(均以秒为单位):
- 最长至少有一人在挤奶的时间段。
- 最长的无人挤奶的时间段。（从有人挤奶开始算起）
提示：如果直接逐个判断每一时间点的农民挤奶人数，需要比较大的空间开销，而且速度也比较慢。可以先将时间按升序排序，然后从左到右逐个扫描，维护一个当前区间[tmp_begin, tmp_end]，如果下一组数据的begin比tmp_end小（或等于），则时间段是连续的，检查这组数据的en，去max{end, tmp_end}作为tmp_end的值。否则，区间断开，记录下区间长度，继续操作，得到最大的区间长度。此问题的解决方法很多，欢迎同学们使用自己的方法，如果非常巧妙，可以考虑加分。
【输入形式】
第一行为整数N，之后N行每行两个小于1000000的非负整数，表示每个农民的开始时刻和结束时刻
【输出形式】
最长至少有一人在挤奶的时间和最长的无人挤奶的时间（运行时间1s以内）
【样例输入】
3
300 1000
700 1200
1500 2100
【样例输出】
900 300
【样例说明】
【评分标准】
请大家在程序中写出必要的注释，如果程序没有必要的注释，将酌情扣分。由于本题数据规模较大，如果使用简单的数据结构和算法可能不能够满足时间效率的要求，所以请大家尽量使用比较高级的数据结构和解法，如果未能满足时间要求，我们会根据时间效率来酌情给分，效率越高分值越高。