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

问题描述

假设我有一个区间（A，B），以及一些子区间{（A <子>我，B <子>我）} <子>我其结合是所有的（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.

证明：考虑所有覆盖的子区间的集合S <子>一。显然，它们中的一个具有向属于的最优解。如果我们用一个子区间代替它（<子>最大，B <子>最大）选自S <子>一的右端点B <子>最大是最大的S中<子>一（达到最右侧），剩下的发现时间间隔（B <子>最大，B）将剩余的区间的一个子集的最佳解决方案，因此它可覆盖有不超过从最优解的类似未覆盖间隔更子区间。因此，一个解决方案，从（一个<子>最大，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.

所以，刚开始在和反复挑选间隔到达最远的权利（和覆盖previous间隔结束），重复，直到你打湾我认为，挑选下一个时间间隔可以在日志（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屋！