问题描述:

Given a list of intervals, I would like to identify the non-overlapping subset of that list that occupies the largest total integer range. For example, if the ranges are:

listy = [[0,10],[11,15],[11,12],[20,30]]

then the correct subset of intervals would be [0,10], [11,15] and [20,30], making the max non-overlapping total range equal to (10 + 4 + 10) = 34.

The approaches I keep coming up with seem to involve variations on just brute forcing through all subsets - there has to be a better way!

网友答案:

There most likely isn't a better way. You're trying to solve various instances of the (max) subset sum problem which is NP-complete. Hence there most likely isn't an efficient algorithm for your problem.

相关阅读:
Top