# algorithm - Find non-overlapping ranges with largest total sum of lengths

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.

Then define `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)
``````

Where `I_r` are the intervals that occur before `I_j`.

The time complexity is `O(n^2)` where `n` is the number of intervals.