Search for a subset of disjunctive intervals with maximum weights

Question

I am looking for an algorithm that I could use to solve this problem, not code. I wondered about using linear relaxation programming, but maybe there are more efficient ways to solve this?

Problem

I have a set of intervals with weights. Intervals may overlap. I need to find the maximum sum of the weights of a subset of disjunctive intervals.

Example

Intervals with weights:

  | --3-- |  | --- 1 ----- |
     | ---- 2-- |  | ---- 5 ---- | 

Answer: 8

Answer 1

I have an exact O (nlog n) DP algorithm . Since this is homework, here is the key:

Sort the intervals by the position of the right edge, as Saeed suggests, then number them from 1. Define f (i) as the highest weight achievable using only intervals that do not extend to the right of the right edge of interval i.

EDIT: Hint 2: Calculate each f (i) in ascending order of i. Keep in mind that each interval will either be present or absent. To calculate the estimate for the “real” case, you will need to look for the “rightmost” interval compatible with interval i, which will require a binary search through the solutions you have already calculated.

It was big, not sure that I could give more clues without fully setting out this;)

Answer 2

If there is no weight, you can use the greedy algorithm, sorting the intervals to their end, and at each step you will get the smallest possible end time interval.

but in your case, I think it's NPC (I have to think about it), but you can use a similar greedy algorithm for the value of each interval using Weigth / Length and each time get one of the possible intervals in a sorted format. You can also use simulated annealing, which means that every time you get the best answer above the value with probability P (p is close to 1 ) or choose another interval with probability 1- P you can do this in a while loop for n times to find a good answer.

Answer 3

Here is an idea:

Consider the following graph: Create a node for each interval. If interval I1 and interval I2 do not overlap, and I1 does not overlap to I2, add a directed edge from node I1 to node I2. Please note that this graph is acyclic. Each node has a cost equal to the length of the corresponding interval.

Now the idea is to find the longest path in this graph that can be found in polynomial time for acyclic graphs (for example, using dynamic programming). The problem is that the costs are in nodes, not in edges. Here's the trick: divide each node v into v 'and v' '. All the edges in v will now be in v ', and all the remaining edges of v will now leave v' '. Then add the edge from v 'to v' 'with the node value, in this case, the length of the interval. All other edges will cost 0.

Well, if I'm not mistaken, the longest path on this graph will correspond to many disjoint intervals with a maximum sum.

Answer 4

You can state this problem as a general problem with IP (integer programming) with binary variables indicating whether the interval is selected or not. Then the objective function will be a weighted linear combination of variables. Then you will need appropriate constraints to ensure disjunctivity between intervals ... This should be enough with the homework tag.

In addition, just because the problem can be formulated as an integer program (whose solution is NP-Hard), this does not mean that the problem class itself is NP-Hard. So, as Ulrich points out, there may exist a polynomially solvable formulation / algorithm, such as the formulation / solution of a problem as a linear program.

Answer 5

This explains the correct solution (from end to end): http://tkramesh.wordpress.com/2011/02/03/dynamic-programming-1-weighted-interval-scheduling/