找到重叠区间的最小子集

Question

考虑一个问题来寻找区间图的最小支配集。在区间调度的上下文中，它被转换为以下问题：

存在多个可能相互重叠的间隔。找到区间的最小子集，以便对于未包含在子集中的每个区间，它将在与它重叠的子集中找到至少1个区间。

有一个公认的贪婪解决方案可从互联网上的各种来源，例如康奈尔大学的一个解决方案：http://www.cs.cornell.edu/Courses/cs4820/2011sp/handouts/samplesolutions.pdf

我们的工作是填充一组C，组成委员会（区间子集）。我们使用一组M来保持“覆盖”的时间间隔以便记账。

1. 按最早完成时间和最早完成时间对间隔进行排序。
2. 取S中最早完成时间的间隔i。
3. 构造集O={s≥S|s相交i}
4. 取最晚结束时间的o⑵O并将o加到C，将所有与o相交的区间加到M
5. 重复2-4，直到覆盖所有间隔。

这类似于interjay在2012年SO上提供的投票结果：找到最小的重叠作业集

但我注意到一个反例，证明上述解决方案不产生最小子集：

考虑区间：[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]在步骤4被过早拒绝。

还有比上面贴的更好的贪婪解决方案吗？谢谢！

Answer 1

你引用的算法是不正确的，因为集合S永远不会改变，所以在第2步中，将始终选取相同的间隔，并且你将进入一个无限循环。如果将步骤2更改为“以最早完成时间为单位，以S-M为间隔i。”，这将是正确的。

然而，你所链接的我的答案是正确的。它和上面的修正算法都将给出一个集{[1,4]，[3,10]}，作为您的示例。

您所犯的错误可能是，在上面的步骤3（或我的链接答案中的步骤2）中，您只查看S-M中的集合（在我的答案中称为A）。但你应该看看所有与i相交的间隔，即使它们已经在M中了。