从a或b开始的贪心算法总是可以提供最佳解决方案。

证明：考虑集合S 一个全覆盖的子区间。显然，其中之一必须属于最佳解决方案。如果将其替换为S a的子间隔（a max，b max），其右端点b max在S
a中最大（最右侧），则剩余的未覆盖间隔（b max，b）将是最佳解决方案的剩余间隔，因此可以覆盖的子间隔不超过最佳解决方案的类似未覆盖间隔。因此，由（a
max，b max）和剩余间隔的最佳解决方案（b max，b）也是最佳的。

因此，只需从a开始，然后反复选择到达最右端的间隔（并覆盖上一个间隔的末尾），重复直到您按b。我相信，如果将间隔存储在扩展间隔树中，则可以在log（n）中选择下一个间隔。