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

区间部署

2012-08-17 
区间调度?问题:有一组需求{1,...,n},每个需求i有一个开始结束时间s(i),f(i)对应,如果两个需求没有在时间上

区间调度

?

问题:有一组需求{1,...,n},每个需求i有一个开始结束时间s(i),f(i)对应,如果两个需求没有在时间上重叠,我们就说需求是相容的,求最大的相容子集,即最优子集。

?

明显的贪心算法啦:

??按照f结束时间升序排序,O(nlogn),

? 依次处理每个需求,假如最优子集集合,顺序删除与之冲突的后续需求,O(n)

?

热点排行