首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > 编程 >

USACO Section 1.2.1 [Milking Cows] Java例题

2012-11-01 
USACO Section 1.2.1 [Milking Cows] Java题解题意分析:输入为N组 [900,1800],[1200,2200] 这样的[开始,结

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

热点排行