USACO Section 1.2.1 [Milking Cows] Java题解
题意分析:
输入为N组 [900,1800],[1200,2200] 这样的[开始,结束]时间段。要求计算最长连续时间长度,以及最长中断的时间长度。
解题思路:
首先:将输入中的时间段按开始时间排序。
然后:处理重叠的时间段,为后续计算做准备。
if(a.end <= b.start) then do nothing
else if (a.end > b.start && a.end < b.end) then a.end = b.start
else b.start=b.end=a.end
最后:计算出最长连续时间长度,以及最长中断的时间长度。
该算法时间复杂度O(n)
代码实现:
https://github.com/leonlu/USACOJavaSolution/blob/master/USACOSection1/src/milk2.java