最大事件拦截

Question

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

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

我知道什么？

我知道活动ID、开始时间和结束时间。我还有 坐标.

什么是最大事件重叠？

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

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

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

Answer 1

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

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

2- 将每个事件拆分为两个事件：

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

• (结束时间,-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.

中找到