问题描述
这是那里的算法专家的一个问题:-)
this is a question for the algorithms gurus out there :-)
让S
是一组可能重叠的自然数的间隔,而b
是一个框的大小.假设对于每个时间间隔,范围都严格小于b
.
Let S
be a set of intervals of the natural numbers that might overlap and b
a box size. Assume that for each interval, the range is strictly less than b
.
我想找到大小为b
的最小间隔集(我们称它为M
),因此S
中的所有间隔都包含在M
的间隔中.
I want to find the minimum set of intervals of size b
(let's call it M
) so all the intervals in S
are contained in the intervals of 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]
我认为贪婪算法可能无法始终有效,因此,如果有人知道该问题的解决方案(或可以转换为类似方案的解决方案),那就太好了.
I think a greedy algorithm might not work always, so if anybody knows of a solution to this problem (or a similar one that can be converted into), that would be great.
谢谢!
更新我一直在想更多,也许我的第一个直觉是错误的,贪婪的算法只是解决这个问题的方法,因为最终所有间隔都需要被覆盖,选择超级间隔不会有任何区别...我应该删除问题还是应该有人可以断言?
Update I've been thinking a little bit more about it, and maybe my first intuition was wrong and a greedy algorithm is just the way to solve this, as in the end all the intervals need to be covered and it wouldn't make any difference how the super-intervals are chosen... Should I delete the question or maybe somebody can assert this?
推荐答案
算法可能如下.
- a = 0
- curr = S中的最低数字,即> a. (在我们的例子中,在[1..4]中= 1.)
- 为M添加一个间隔[curr..b](在我们的情况下,M = {[1..10]})
- a =以M为单位的最大上限(在我们的示例中,a = 10)
- 转到2.
这篇关于减少覆盖给定间隔的盒子的数量的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!