algorithm - 用给定的间隔覆盖所有数字

Question

这是算法专家的问题:-)

设 S 是一组可能重叠的自然数区间，N 是一个数字列表。

我想找到 S 的最小子集(我们称之为 P)，这样对于每个数字 在我们的列表 N 中，P 中至少存在一个包含它的区间。 P 中的区间允许重叠。

简单的例子:

S = {[1..4], [2..7], [3..5], [8..15], [9..13]}
N = [1, 4, 5]
// so P = {[1..4], [2..7]}

我认为动态算法可能并不总是有效，所以如果有人知道这个问题的解决方案(或可以转换成的类似解决方案)，那就太好了。

谢谢!

Answer 1

您可以使用贪心算法来做到这一点。

按顺序考虑 N 中的点。

对于每个点，如果它已经被一个区间覆盖则跳过它。

否则，考虑包含该点的区间。从这些间隔中，选择覆盖最多未覆盖点的间隔。 (这将是具有最高终点的区间。)

示例

1. 第一个点是 1，仅被 1..4 覆盖，因此将此间隔添加到我们的集合中。
2. 下一点是 4，但它已经涵盖了所以继续。
3. 下一点是 5，由 2..7 和 3..5 涵盖。选择其中任何一个来获得包含 2 套所有要点的答案。