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

Maximum range occupied by nonoverlapping intervals in python

问题描述:

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.

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