用子区间查找区间的最小覆盖 [英] Finding the minimal coverage of an interval with subintervals

问题描述

假设我有一个区间 (a,b) 和多个子区间 {(a_i,b_i)}_i其并集是 (a,b) 的全部.有没有一种有效的方法来选择这些子区间的最小基数子集，它仍然覆盖 (a,b)?

Suppose I have an interval (a,b), and a number of subintervals {(a_i,b_i)}_i whose union is all of (a,b). Is there an efficient way to choose a minimal-cardinality subset of these subintervals which still covers (a,b)?

推荐答案

从 a 或 b 开始的贪心算法总是给出最优解.

A greedy algorithm starting at a or b always gives the optimal solution.

证明:考虑覆盖a的所有子区间的集合S_a.显然，其中之一必须属于最优解.如果我们用右端点 b_max 的 S_a 的子区间 (a_max,b_max) 替换它在 S_a 中最大(到达最右边)，剩余的未覆盖区间 (b_max,b) 将是最优解的剩余区间的子集，所以它不能被比最优解的类似未覆盖区间更多的子区间覆盖.因此，由 (a_max,b_max) 和剩余区间 (b_max,b) 的最优解构成的解也将是最优的.

Proof: consider the set S_a of all the subintervals covering a. Clearly, one of them has to belong to the optimal solution. If we replace it with a subinterval (a_max,b_max) from S_a whose right endpoint b_max is maximal in S_a (reaches furthest to the right), the remaining uncovered interval (b_max,b) will be a subset of the remaining interval from the optimal solution, so it can be covered with no more subintervals than the analogous uncovered interval from the optimal solution. Therefore, a solution constructed from (a_max,b_max) and the optimal solution for the remaining interval (b_max,b) will also be optimal.

所以，只需从 a 开始，然后迭代地选择到达最右边的区间(并覆盖前一个区间的末尾)，重复直到你点击 b.我相信如果您将区间存储在扩充区间树中，则可以在 log(n) 中选择下一个区间.

So, just start at a and iteratively pick the interval reaching furthest right (and covering the end of previous interval), repeat until you hit b. I believe that picking the next interval can be done in log(n) if you store the intervals in an augmented interval tree.

这篇关于用子区间查找区间的最小覆盖的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！