algorithm - 最大事件拦截

Question

我正在尝试找出一种算法来检测随时间推移的最大事件交集数。下图将说明情况。

我有多个可以重叠的事件，我必须确定所有事件之间的最大重叠是多少。

我知道什么？

我知道事件ID、开始时间和结束时间。我也有坐标。

什么是最大事件重叠？

如图所示，最大值为3。这是因为一次只有 3 个事件重叠。例如 ID:1,3,4 或 1,3,5。

我有一个需要很多周期的解决方案。但是我想不出一些适合具有许多事件的 Web 应用程序的快速优雅的解决方案。

提前感谢您的所有回答。如果您发现一些语法错误，请编辑帖子。谢谢。

Answer 1

使用扫描线算法。以下是它在您的情况下应该如何工作:

1- 创建一个名为 sweep 的向量。

2- 将每个事件分成两个事件:

• (start time, 1):这里的1表示第一部分表示开始时间。

• (end time, -1):这里的-1表示第一部分表示结束时间。

  <

3- 将新事件插入向量 sweep。

4- 以第一部分的递增顺序对创建的向量进行排序，以防在第二部分的递增顺序中出现平局。

5- 现在下面的伪代码应该可以回答您的问题:

int answer = 0, eventsCount = 0;
for(int i = 0 -> sweep.size()){
    eventsCount += sweep[i].second;
    answer = max(answer, eventsCount);
}

这里的 eventsCount 表示当前打开的事件数，而 answer 表示您目前为止的最佳答案。最后，您的问题的答案将在变量 answer 中找到。