最小化覆盖给定间隔集的框数
这是算法大师的问题:-)
令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]
我认为贪婪算法可能并不总是有效，所以如果有人知道这个问题的解决方案（或可以转换成的类似问题），那就太好了。
谢谢！
更新我一直在思考这个问题，也许我的第一直觉是错误的，贪心算法只是解决这个问题的方法，因为最终需要覆盖所有区间并且如何选择超级间隔不会有任何区别......我应该删除这个问题还是也许有人可以断言这一点？
this is a question for the algorithms gurus out there :-)
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.
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.
Trivial example:
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.
Thanks!
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?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
该算法可能如下。
The algorithm might be the following.
是的，贪心算法是最优的。非正式地，考虑任意解 M。我们将其转换为贪婪解 M' 的超集，而不增加间隔的数量。反复考虑 M - M' 中最左边的区间 I。令 s 为 S 中最左边的区间，其中 I 为 M 中包含 s 的最左边区间。从左到右的贪心算法选择一个区间 I'，其左边缘与 s 的边缘对齐。我首先声称 I' 在 I 的右侧，因为 I' 是包含 s 的最右边的区间，其次，M - {I} U {I'} 是一个有效的解，因为 I 包含的唯一区间但不是 I' 在 s 的左侧，因此已经包含在其他某个区间中。不在贪婪解中的区间数量减少，因此我们最终达到贪婪解。
Yes, the greedy algorithm is optimal. Informally, consider an arbitrary solution M. We will transform it into a superset of the greedy solution M' without increasing the number of intervals. Repeatedly consider the leftmost interval I in M - M'. Let s be the leftmost interval in S for which I is the leftmost interval in M to contain s. The left-to-right greedy algorithm chooses an interval I' whose left edge is aligned with s's. I claim first that I' is to the right of I, since I' is the rightmost interval to contain s, and second, that M - {I} U {I'} is a valid solution, since the only intervals contained by I but not I' are to the left of s and thus already contained by some other interval. The number of intervals not in the greedy solution decreases, so we eventually reach the greedy solution.