查找具有子间隔的间隔的最小覆盖范围

假设我有一个区间(a,b),以及多个子区间{(a _i,b _i)} _i,其并集都是(a,b).是否有一种有效的方法来选择这些子区间的最小基数子集,这些子集仍然涵盖(a,b)？

从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)中选择下一个间隔.