我正在寻找可以用来解决这个问题的算法，而不是代码。我想知道如何使用松弛的线性规划，但也许有更有效的方法来解决这个问题？
问题
我有一组带权重的区间。间隔可以重叠。我需要找到析取区间子集的最大权重和。
示例
权重区间:
|--3--| |---1-----|
|----2--| |----5----|
答案:8
最佳答案
我有一个精确的 O(nlog n) DP 算法。由于这是家庭作业，这里有一个线索:
按照 Saeed 的建议按右边缘位置对区间进行排序，然后从 1 开始对它们进行编号。将 f(i) 定义为仅使用不延伸到区间 i 右边缘右侧的区间可获得的最高权重。
编辑:线索 2: 以 i 的递增顺序计算每个 f(i)。请记住，每个间隔要么存在，要么不存在。要计算“当前”情况的分数，您需要寻找与区间 i 兼容的“最右边”区间，这将需要对您已经计算的解决方案进行二分搜索。
那是个大问题，不确定我能否在不完全拼写出来的情况下提供更多线索 ;)
关于algorithm - 寻找具有最大权重的析取区间的子集，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4354988/