如何确定一组区间是否能够在特定成本下覆盖一个区域？

Question

3

我有一组区间，每个区间都有一个成本。例如：

[(0, 4, 10), (2, 6, 5), (5, 7, 2), (8, 10, 2), (5, 10, 10)]

我想知道是否存在一组区间子集，能够准确地覆盖整数1…10（例如），且彼此之间不重叠，并且总成本低于给定值 c 。覆盖的成本是覆盖中各个区间成本的乘积。

在这种情况下，我们可以使用[(0,4,10), (5,10,10)]来精确覆盖该间隔，其成本为 10 * 10 = 100 。或者我们可以使用[(0,4,10)，(5,7,2)，(8,10,2)]来覆盖该间隔，其成本为 10 * 2 * 2 = 40 。

因此，如果我们将成本设置为 c = 50 ，则答案将为YES，如果我们将 c = 30 ，则答案将为NO。

有没有有效的方法来解决这个问题？

我在想是否有某种变体的加权区间调度可以解决，但我看不出如何进行所需的修改。主要问题是，这里我们只关心覆盖整个区间且没有重叠的覆盖，并且我们想要使这些覆盖的成本最小化。

- Simd

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Christian Sloper · Accepted Answer

编辑：请注意@btillys评论中关于使用log(cost)作为边权重的建议，这很重要，因为我们希望成本的乘积，而不是总和。

是的，有一种有效的方法可以通过图论来解决这个问题。

让每个区间（a，b，cost）成为节点v，并让e成为两个节点v1 = (a，b，cost)和v2 = (a2，b2，cost2)之间的边，如果'a2 = b+1'（非正式地：你可以使用v2从v1过渡）。

有一个起始节点s，它与所有具有a=0的节点相连，还有一个完成节点f，它连接到所有b=10的节点。

现在，问题被简化为找到s和f之间的最短路径。使用Djikstra或类似方法，复杂度应为O(E + VlogV)