algorithm - 区间选择算法

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] 最大，则贪心算法对第一个输入的回答不正确。