嗯,我觉得这很难解释,所以我画了一个图来说明这一点。
正如我们在这张图中看到的,有 6 个时间间隔。每一个都有它的重量。不透明度越高,权重越高。我想要一种算法来找到总重量最高的区间。在图中,它是间隔 5 和 6 的重叠,这是不透明度最高的区域。
最佳答案
将每个区间分成起点和终点。
对点进行排序。
从 0 开始。
使用 sweep-line algorithm 遍历点:
如果你有一个起点:
将总和增加相应区间的值。
如果总和计数高于迄今为止的最佳总和,则存储此起点并设置标志。
如果你得到一个终点:
如果设置了标志,则将存储的起始点和此结束点与当前总和作为迄今为止的最佳间隔存储并重置标志。
将计数减少相应间隔的值。
这源自the answer I wrote here ,这是基于未加权的版本,即找到重叠间隔的最大数量,而不是最大总和权重。
示例:
对于这个例子:
开始/结束点将排序为:(S
= 开始,E
= 结束)
1S, 1E, 2S, 3S, 2E, 3E, 4S, 5S, 4E, 6S, 5E, 6E
遍历它们,您将在 1S
、5S
和 6S
上设置标志,并将相应的间隔存储在1E
、4E
和 5E
(这是您在上述起点之后到达的第一个终点)。
您不会在 2S
、3S
或 4S
上设置标志,因为总和将低于目前为止的最佳总和.
关于找到加权重叠区间的总权重最高的区间的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22748269/