问题描述
假设我有一个区间（A，B），以及一些子区间{（A ，B ）和对剩余的间隔的最优解构造（二，二）也将是最佳的。
Proof: consider the set S 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,b) from S whose right endpoint b is maximal in S (reaches furthest to the right), the remaining uncovered interval (b,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,b) and the optimal solution for the remaining interval (b,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.
这篇关于寻找具有子区间的区间的最小覆盖的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！