How to find if a set of intervals can cover a region below a certain cost?

user_1473517 0
Viewed 79

I have a set of intervals each of which comes with a cost. For example

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

I would like to know if there is a subset of the intervals that covers the integers 1...10 (say) exactly without overlapping each other and with total cost below a given value c. The cost of a covering is the product of the costs of the intervals in the cover.

In this case we can cover the interval exactly with [(0, 4, 10), (5, 10, 10)] which has cost 10*10=100. Or we can cover the interval with [(0,4,10), (5, 7, 2), (8, 10, 2)] which has cost 10*2*2 = 40.

So if we had set the cost c=50 then the answer would be YES and if we had set c=30 the answer would be NO.

Is there an efficient way to solve this problem?

I was wondering if some variant of weighted interval scheduling might do it but I can't see how to do the required modification. The main problem is that here we only care about coverings that cover the entire interval without overlaps and we want to minimize the cost for those.

algorithm python
1 Answers

Edit: Note @btillys comment about using log(cost) for weight of the edges, this is important since we want the product of costs, not the sum.

Yes, there is a efficient way to solve this through graph theory.

Let each interval (a,b, cost) be a node v, and let e be an edge between two nodes v1 = (a,b, cost) and v2 = (a2,b2, cost2) iff 'a2 = b+1' (informally: you can use v2 coming from v1).

Have a start node s that has an edge to all nodes with a=0 and a finish node f that has an edge to all nodes b=10.

The problem is now reduced to finding the shortest path between s and f. Using Djikstra or similar the complexity should be O(E + VlogV)

user_81117550
Related