寻找重叠所有其他区间的最小区间集的贪婪算法
寻找重叠所有其他区间的最小区间集的贪婪算法
提问于 2015-10-27 16:01:18
我正在学习贪婪的算法，遇到了一个我不知道该如何解决的问题。给定一组具有开始时间a和结束时间b的间隔(a，b)，给出一种贪婪的算法，该算法返回集合中每一个其他间隔重叠的最小间隔量。例如，如果我有：
(1,4) (2,3) (5,8) (6,9) (7,10)
我将返回(2,3)和(7,8)，因为这两个区间涵盖了集合中的每个区间。我现在要说的是：
- 通过增加结束时间对间隔进行排序
- 将结束时间最小的间隔推到堆栈上。
- 如果间隔(a，b)与堆栈(c，d)顶部的间隔重叠(所以a小于d)，那么如果a<=c保持(c，d)。否则，将堆栈顶部的间隔更新为(a，d)
- 如果间隔(a，b)不重叠堆栈(c，d)顶部的间隔，则将(a，b)推到堆栈上。
- 最后，堆栈包含所需的间隔，这应该在O(n)时间内运行。
我的问题是:这个算法怎么会贪婪？我在为这些概念而挣扎。所以也许我有这个权利，也许我没有，但如果我这样做了，我不知道贪婪的规则是什么/应该是什么。
编辑:下面提出了一个有效的观点，对此我应该更清楚一些。(7,8)工作，而不是(1,10) (涵盖一切)，因为每次(7,8)是在(5,8) (6,9)和(7,10)。与(2,3)相同，每次都在(1,4)和(2,3)中。目标是得到一组间隔，这样，如果您在这组间隔中查看所有可能的时间，那么每次都至少在一个原始的时间间隔内。
回答 1
Stack Overflow用户
发布于 2015-10-28 01:54:43
贪婪算法是一种反复选择最佳增量改进的算法，即使从长远来看，它可能是次优的。
在我看来你的算法并不贪婪。对于这个问题，一个贪婪的算法是：
- 从输入集中查找包含在最大间隔数中的间隔。
- 从包含它的输入集中删除间隔。
- 重复，直到输入集为空。
对于这个例子，它将首先生成(7,8)，因为它包含在3个输入间隔中，然后将输入集缩减为(1,4) (2,3)，然后生成(2，3)。
请注意，该算法没有为输入集产生最佳输出：(0,4)(1,2)(1,4)(3,6)(3,7)(5,6)
它首先生成(3,4)，因为它由4个输入间隔覆盖，但最好的答案是(1,2)(5,6)，每间隔3次。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/33372763
复制相关文章
相似问题
腾讯云开发者
