algorithm - 贪婪地删除冲突最多的区间是否解决了区间调度问题？

Question

我们可以解决调度问题，其中我们必须使用贪心算法选择最大的一组不重叠的连续间隔:我们只是不断选择最早结束的间隔:http://en.wikipedia.org/wiki/Interval_scheduling

显然，贪婪地选择冲突最少的区间是行不通的。

我想知道将所有间隔放在一个大集合中然后贪婪地删除剩余冲突数量最多的间隔(直到间隔没有冲突)是否有效。我可以设想用优先级队列实现这个贪心算法:每次我们从优先级队列中删除具有最大冲突的区间 X 时，我们更新过去与区间 X 冲突的其他区间，以便其他区间现在被标记为具有 1减少冲突。

这个有用吗？我正试图想出一个反例来反驳它，但做不到。

Answer 1

这是一个反例。这个想法是在第一次选择时放弃所需的间隔。右边是冲突次数。

        ====    2
       ----     3
      ----      3
    ====        4
  ----          3
 ----           3
====            2

显然，我们要选择三个粗体 (====) 间隔并删除四个细 (----) 间隔。没有其他方法可以得到三个不相交的区间。

顺便说一下，您可能会找到 TopCoder tutorial关于贪心问题很有趣，因为它从讨论同一问题的几种方法开始。