当前位置: 动力学知识库 > 问答 > 编程问答 >

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.

分享给朋友:
您可能感兴趣的文章:
随机阅读: