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]中的最大区间有3种可能。如果 [0,2] 或 [3,5] 是最大值，则贪心算法分别对第二个或第三个输入做出不正确的回答。如果 [1,4] 最大，则贪心算法对第一个输入的回答不正确。