这是算法大师的问题:-)
让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]
我认为贪心算法可能并不总是有效,所以如果有人知道这个问题的解决方案(或可以转换成的类似问题),那就太好了。
谢谢!
更新我一直在考虑更多关于它,也许我的第一个直觉是错误的,贪婪算法就是解决这个问题的方法,因为最后所有的间隔都需要被覆盖,它不会使任何选择超级间隔的方式不同......我应该删除这个问题还是有人可以断言这个?