找到重叠区间的最小子集
考虑一个问题，以求区间图的最小支配集。在间隔时间安排方面，将其转换为以下问题：
有多个间隔，它们可以或可能相互重叠。找出间隔的最小子集，这样对于不包括在子集中的每一个区间，它将在与其重叠的子集中找到至少一个区间。
互联网上有一个一致同意的贪婪解决方案，例如康奈尔大学的一个解决方案：http://www.cs.cornell.edu/Courses/cs4820/2011sp/handouts/samplesolutions.pdf
我们的工作是填充一个组成委员会的集合C(间隔子集)。我们使用集合M来保持记账的“覆盖”间隔。
- 按照完成时间和最早的完成时间对间隔进行排序。
- 以I在S中的间隔和最早的完成时间。
- 构造集合O= {s∈S_s_s_s交叉i}
- 取O∈O和最近的完成时间，并将o添加到C，添加与o到M相交的所有间隔
- 重复2-4，直到所有间隔都被覆盖。
这类似于interjay在2012年在SO：Find the smallest set of overlapping jobs上提供的投票结果。
但是我注意到了一个反例，它证明了上面的解决方案没有产生最小子集：
考虑间隔: 0,2，1,4，3, 10，5，6，7,8，9，10。
一个最小子集应该有两个间隔: 3，10加上0，2或1，4。
但上述解将返回4个区间的子集: 1, 4，5,6，7,8和9,10。最长的间隔3,10在第4步被提前拒绝。
有没有比上面贴的更好的贪婪解决方案？谢谢!
回答 1
Stack Overflow用户
发布于 2014-10-02 23:58:17
您引用的算法是不正确的，因为集合S永远不会改变，所以在步骤2中，总是会选择相同的间隔，然后进入无限循环。如果你将第二步改为“以最快的完成时间在S中的间隔I”，它将是正确的。
但是，您链接的My answer是正确的。它和上面的修正算法都会给出你的例子的集合{1,4，3,10}。
您所犯的错误可能是，在上面的步骤3(或我链接的答案中的步骤2)中，您只查看在S中的集合(在我的答案中称为A)。但是你应该看看i相交的所有间隔，即使它们已经在M中。
https://stackoverflow.com/questions/26170904
复制相似问题
腾讯云开发者
