这是算法专家们的问题:-)
设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]
我认为贪婪的算法可能并不总是有效的,所以如果有人知道这个问题的解决方案(或者类似的算法可以转换成),那就太好了。
谢谢!
更新我一直在想更多关于它,也许我的第一直觉是错误的,贪婪的算法只是解决这个问题的方法,因为最后所有的间隔都需要被覆盖,它不会有任何区别如何选择超级间隔我应该删除这个问题,还是有人可以断言?
最佳答案
算法可能如下。
A=0
curr=S中的最小值,大于a(在我们的例子中为1)在[1..4]中)
将间隔[curr..b]添加到m。(在我们的示例中,m={[1..10]})
A=最大上界(m)(在我们的情况下,A=10)
转到2。
关于algorithm - 减少覆盖给定间隔的盒子的数量,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/2493721/