找到加权重叠区间的最高加权重的区间的算法

Question

嗯,我觉得很难解释,所以我已经做了一个数字来表明这一点.

正如我们在该图中所看到的,有6个时间间隔.每个人都有自己的体重.不透明度越高,重量越高.我想要一个算法来找到具有最高总重量的区间.在该图的情况下,它是间隔5和6的重叠,其是具有最高不透明度的区域.

Answer 1

• 将每个间隔分成开始点和结束点.

• 对点进行排序.

• 以0的总和开始.

• 使用扫描线算法迭代这些点:

  • 如果你有一个起点:

    • 通过相应间隔的值增加总和.

    • 如果总计数高于目前为止的最佳总和,则存储此起始点并设置标志.

  • 如果你得到一个终点:

    • 如果设置了标志,则将存储的起点和此终点存储为当前总和作为目前为止的最佳间隔并重置该标志.

    • 将计数减少相应间隔的值.

这源于我在这里写的答案,它基于未加权的版本,即找到重叠间隔的最大数量,而不是最大总和权重.

例:

对于这个例子:

起点/终点将排序为:(S= start,E= end)

1S, 1E, 2S, 3S, 2E, 3E, 4S, 5S, 4E, 6S, 5E, 6E

通过它们进行迭代,你将设置标志1S,5S并且6S,你将各自的间隔存储在1E,4E和5E(这是你在上述起点之后得到的第一个终点).

您不会设置标志2S,3S或者4S,因为总和将低于目前为止的最佳总和.