python - python中非重叠间隔占用的最大范围

Question

给定一个区间列表，我想确定该列表中占据最大总整数范围的非重叠子集。例如，如果范围是：

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

那么正确的区间子集将是 [0,10]、[11,15] 和 [20,30]，使得最大非重叠总范围等于 (10 + 4 + 10) = 34。

我不断提出的方法似乎涉及对所有子集进行暴力破解的变化——必须有更好的方法！

Answer 1

很可能没有更好的方法。您正在尝试解决 NP 完全的（最大）子集和问题的各种实例。因此，很可能没有针对您的问题的有效算法。