我有一组间隔，每个间隔都有成本。例如
[(0, 4, 10), (2, 6, 5), (5, 7, 2), (8, 10, 2), (5, 10, 10)]
我想知道是否有一个子区间完全覆盖整数1…10(比如说(，而彼此不重叠，并且总成本低于给定值c。覆盖层的成本是覆盖层中间隔成本的乘积。
在这种情况下，我们可以用具有成本10*10=100的[(0，4，10(，(5，10，10(]精确地覆盖区间。或者我们可以用[(0,4,10(，(5,7,2(，(8,10,2(]覆盖区间，其代价为10*2*2 = 40。
因此，如果我们设置了成本c=50，那么答案将是YES，如果我们设定了c=30，答案将是NO。
有有效的方法来解决这个问题吗？
我想知道加权间隔调度的某些变体是否可以做到这一点，但我不知道如何进行所需的修改。主要问题是，在这里，我们只关心覆盖整个区间而没有重叠的覆盖物，我们希望将这些覆盖物的成本降至最低。
编辑：注意@btillys关于使用log(cost(表示边的重量的评论，这很重要，因为我们想要成本的乘积，而不是总和。
是的，有一种有效的方法可以通过图论来解决这个问题。
设每个区间(a，b，cost(是节点v，设e是两个节点v1 = (a,b, cost)和v2 = (a2,b2, cost2)之间的边，当'a2=b+1'时(非正式地：您可以使用来自v1的v2(。
具有到具有a=0的所有节点具有边的开始节点s和到所有节点b=10具有边的结束节点f。
现在问题简化为寻找s和f之间的最短路径。使用Djikstra或类似方法，复杂性应为O(E + VlogV)