减少覆盖给定间隔的盒子的数量 [英] Minimizing the number of boxes that cover a given set of intervals

问题描述

这是那里的算法专家的一个问题:-)

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?

推荐答案

算法可能如下.

1. a = 0
2. curr = S中的最低数字，即> a. (在我们的例子中，在[1..4]中= 1.)
3. 为M添加一个间隔[curr..b](在我们的情况下，M = {[1..10]})
4. a =以M为单位的最大上限(在我们的示例中，a = 10)
5. 转到2.

这篇关于减少覆盖给定间隔的盒子的数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！