问题描述
考虑一个问题，找到一个最小支配集间隔图形。在间隔调度的情况下，它被转换为下面的问题：
有多个间隔可被或相互重叠。发现间隔的最小的子集，使得对于未包含在所述子集中的每个间隔，就会发现至少1间隔的子集，将与它重叠。
有一个约定贪婪的解决方案可从互联网上的不同来源，康奈尔等为一体的解决方案： http://www.cs.cornell.edu/Courses/cs4820 /2011sp/handouts/samplesolutions.pdf
这是类似于在SO在2012年提供的interjay一个投了答案：找到最小的一组重叠的工作
不过，我注意到一个反例，证明上述方案不会产生最低的子集：
考虑间隔：[0,2]，[1,4]，[3,10]，[5,6]，[7,8]，[9,10]
一个最小子集应具有2间隔：[3，10]加上任一[0,2]或[1,4]
但是，上述解决方案将返回的4个间隔的一个子集：[1,4]，[5,6]，[7,8]和[9,10]。最长的区间[3,10]是prematurely拒绝在第4步。
有没有比那些上面贴一个更好的贪婪的解决方案？谢谢！
你所引用的算法不正确，因为集合S永远不会改变，所以在第2步相同的时间间隔总是会挑，你会进入一个无限循环。如果更改步骤2，就拿我的时间间隔在SM与最早完成时间，这将是正确的。
您链接我的回答是正确不过。它和上面的修正算法将给集合{[1,4]，[3,10]}为你的榜样。
您正在做的可能是，在上述步骤3（或在我的链接回答步骤2）你正在寻找只在集这是在SM的错误（称为A在我的答案）。但是，你应该看看相交我所有的时间间隔，即使他们已经在并购。
Consider a question to find a minimum dominating set of an interval graph. In the context of interval scheduling, it is converted to the question below:
There are multiple intervals which may or may overlap with each other.Find a minimum subset of the intervals, so that for every interval that is not included in the subset, it will find at least 1 interval in the subset that will overlap with it.
There is an agreed greedy solution available from various sources on the Internet, such as one solution from Cornell:http://www.cs.cornell.edu/Courses/cs4820/2011sp/handouts/samplesolutions.pdf
This is similar to a voted up answer provided by interjay in 2012 on SO:Find the smallest set of overlapping jobs
But I have noticed a counterexample that proves the above solution does not produce the minimum subset:
Consider intervals: [0,2], [1,4], [3,10], [5, 6], [7,8], [9, 10].
A minimum subset should have 2 intervals: [3, 10] plus either [0, 2] or [1, 4].
But the above solution will return a subset of 4 intervals: [1,4], [5,6], [7,8] and [9,10]. The longest interval [3,10] was prematurely rejected at step 4.
Is there a better greedy solution than the ones posted above? Thanks!
The algorithm you quoted is incorrect because the set S never changes, so in step 2 the same interval will always be picked and you will enter an infinite loop. If you change step 2 to "Take the interval i in S-M with earliest finish time.", it will be correct.
My answer which you linked is correct however. Both it and the corrected algorithm above will give the set {[1,4], [3,10]} for your example.
The mistake you're making may be that in step 3 above (or step 2 in my linked answer) you're looking only at sets which are in S-M (called A in my answer). But you should look at all intervals that intersect i, even if they are already in M.
这篇关于找到重叠间隔的最小的子集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！