最小化，涵盖一组给定的时间间隔

Question

的箱子的数量，这是对的算法大师一个问题在那里:-)

让S是一组自然数的区间的可能重叠，b一箱尺寸。假设对于每个间隔，范围严格小于b。

我想找到的最小集合大小b的间隔（我们称之为M）所以在S所有时间间隔都包含在M间隔。

简单的例子：

S = {[1..4], [2..7], [3..5], [8..15], [9..13]} 
b = 10 
M = {[1..10], [8..18]} 
// so ([1..4], [2..7], [3..5]) are inside [1..10] and ([8..15], [9..13]) are inside [8..18] 

我认为贪心算法可能并不总是有效，所以如果有人对这个问题的解决方案（或类似一个可以转换成）的人都知道，这将是巨大的。

谢谢！

更新我一直在思考多一点吧，也许我的第一直觉是错的，贪婪算法就是解决这个问题的方法，在结束时，所有的间隔需要被覆盖，如何选择超级间隔不会有什么区别......我应该删除问题还是有人可以断言这个问题？

Answer 1

算法可能如下。

1. α= 0
2. CURR =最低数S中是>一个。 （在我们的案例中= 1.在[1..4]中）
3. 向M添加区间[curr..b]（在本例中M = {[1..10]}）
4. a =最大值在M.上限（在我们的情况下，A = 10）
5. 转到2.

Answer 2

是，贪婪算法是最佳的。非正式地，考虑一个任意的解决方案M.我们将它转​​化为贪婪解M'的超集而不增加间隔的数量。重复考虑M-M'中最左边的间隔I.设S是S中最左边的区间，其中I是M中包含s的最左边区间。从左到右的贪婪算法选择左边缘与s对齐的区间I'。我首先声明我是在我的右边，因为我是包含s的最右边的区间，其次，M - {I} U {I'}是一个有效的解，因为我包含的唯一区间但不是我'位于s的左边，因此已经被其他区间所包含。不在贪婪解决方案中的间隔数量减少了，所以我们最终达到了贪婪的解决方案。