如何确定最大数量的同时发生事件的时间？

Question

给出一个历史事件的列表，每个事件运行一定的秒，并且有一个非唯一的开始时间，我如何“最佳”地确定最大事件发生的时间范围？(在本例中，“最好”是将数据集存储在SQL数据库中，因此，我可能在寻找将少量查询与向客户端返回小数据集相平衡的方法；可能需要仔细检查时间间隔中的数百个事件。)

例如，考虑到这些事件：

• 事件1从5开始，运行10
• 事件2从7开始，运行4
• 事件3从9开始，运行2

大多数事件发生在9-10次之间，3个事件同时发生.

出现在脑海中的一种方法是迭代事件发生的整个时间间隔，并在每一点上评估发生在那里的事件数量，然后存储最大值；但肯定有更有效的方法。

Answer 1

由于"max“将在其中一个事件开始时发生，因此您可以进行一个自连接，查找当时正在进行的事件的数量：

SELECT TOP 1 MAX(e1.StartDate), COUNT(e2.eventID) FROM event e1
INNER JOIN event e2 
  on e1.StartDate BETWEEN e2.StartDate 
                      AND DATEADD(second,e2.Duration,e2.StartDate)
GROUP BY e1.EventID
ORDER BY COUNT(e2.eventID) DESC

Answer 2

1.把所有的event begin和event end时间都放在下面的结构中：

struct EventBeginOrEnd
{
bool begin; // True if event begin, false if end
int time;
}

将所有事件放在一个List<EventBeginOrEnd> myEventList和中。

2.少设柜台：

• CurrentEventCount -统计现在发生了多少件事。
• MaxEventsCountSoFar -在一段时间内计算最大事件，直到现在为止。
• TheMaxTime -测量最大值的时间。

3.在myEventList上迭代，并在每个元素中检查他是开始还是结束，如果begin增加CurrentEventCount，则减少。

4.当CurrentEventCount更大时，MaxEventsCountSoFar更新如下：

MaxEventsCountSoFar=MaxEventsCountSoFar;
TheMaxTime=currentElement.time;

请注意，这允许您使用浮点来表示时间，而不仅仅是int，因为您不是在对时间进行迭代，而是对您拥有的事件进行迭代。

由于排序的原因，复杂性是O(n*Log(n))。