Activity 使用贪心法选择问题的不同解决方案

Question

著名的 Activity 选择问题有一个经典的解法，你可以看看 here。

但是现在，我想到了另一个解决方案。让我们看看这个 sudo 代码：

while(!empty(S))
{
   Select interval I $ \in $ S that overlap least number of other intervals;
   Add I to Result;
   Remove all Interval from S that overlap with I;
}

你可以猜到S是我们的输入集，I是S的成员，Result是我们的输出集。

如果我们不关心时间复杂度，这个工作是否高效并且总是结果是最大集合？如果不是，我们什么时候没有高效输出？有例子吗？

谢谢！

Answer 1

您的解决方案并不总是有效。这是一个反例

Activity 使用贪心法选择问题的不同解决方案

Different solution for Activity Selection problem with greedy approach

python

c++

algorithm

greedy