区间选择算法

Question

假设我们有一组间隔[s1,e1],[s2,e2]...[sn,en]

我想找到不重叠区间的子集，并且有最大的聚合时间。

实际上我在找一个贪婪的解决方案。它是否存在？

Answer 1

“贪婪”不是一个正式术语，但为了这个问题，让我们将贪婪算法的类别定义为将先验的全序强加于区间(即独立于输入)并以最大可用区间反复扩展部分解的算法。考虑输入

[0,2],[1,4],[3,5]
[0,2],[1,4]
[1,4],[3,5].

在0,2,1,4,3,5之间存在三种可能的最大间隔。如果0,2或3,5为最大值，则贪婪算法对第二输入或第三输入分别不正确地回答。如果1,4为最大值，则贪婪算法对第一个输入的答案不正确。