algorithm - 寻找具有最大权重的析取区间的子​​集

Question

我正在寻找可以用来解决这个问题的算法，而不是代码。我想知道如何使用松弛的线性规划，但也许有更有效的方法来解决这个问题？

问题

我有一组带权重的区间。间隔可以重叠。我需要找到析取区间子集的最大权重和。

示例

权重区间:

|--3--|          |---1-----|    |----2--| |----5----|

答案:8

Answer 1

我有一个精确的 O(nlog n) DP 算法。由于这是家庭作业，这里有一个线索:

按照 Saeed 的建议按右边缘位置对区间进行排序，然后从 1 开始对它们进行编号。将 f(i) 定义为仅使用不延伸到区间 i 右边缘右侧的区间可获得的最高权重。

编辑:线索 2: 以 i 的递增顺序计算每个 f(i)。请记住，每个间隔要么存在，要么不存在。要计算“当前”情况的分数，您需要寻找与区间 i 兼容的“最右边”区间，这将需要对您已经计算的解决方案进行二分搜索。

那是个大问题，不确定我能否在不完全拼写出来的情况下提供更多线索 ;)