I search algorithm, that will help me in the realization of a problem!
The problem is as follows:
There is a list of ranges, I need to build a list with a subset of non-overlapping ranges (not necessarily adjacent), such that the sum of their lengths is maximum possible.
For example, for an input list
[(-1, 3), (2, 4), (0, 5), (-4, -1)]
the desired output is
[(0, 5), (-4, -1)]
with the sum of lengths (5 - 0) + ((-1) - (-4)) = 5 + 3 = 8
This is the maximum weighted independent set problem with the weights being equal to the length of the intervals.
This can be solved using dynamic programming. Let the intervals be sorted by starting times.
DP[I_j] = maximum weighted set of intervals such that
I_j is chosen and only intervals previous to
I_j are considered. This means the intervals intersecting with
I_j shall not be considered.
DP[I_j] = MAX(DP[I_r]) + Wt(I_j)
I_r are the intervals that occur before
The time complexity is
n is the number of intervals.