1

我有一个内存List<Event>，它的长度可能从 1 到 50000+ 个值不等（不理想，但就是这种情况）。每个都Event包含一个openTime属性和一个closedTime存储为的属性Long。

鉴于事件可能重叠，我需要确定NO事件处于活动状态的时间量。当您以图形方式查看它时，它并不是很困难。

在此处输入图像描述

我已经实施了几个解决方案，但我发现很难找到一个对时间资源没有重大影响的解决方案！我目前的解决方案包括；

  1. 遍历集合；对于每个值，我通过迭代并在范围内查找任何值来确定集合中的任何其他值是否重叠。
  2. 在范围内每毫秒（大约 60000 - 即 1 小时）递增循环，并查看当时是否有任何收集元素处于活动状态。

这些都不是性能友好的，所以任何关于实现这一目标的有效方法的建议都会非常感激？

4

1 回答 1

1

类事件 { int start, end; }

使用快速排序对事件进行如下排序：

  1. 开始时间小于事件 y 开始时间的事件 x 必须首先出现在数组中。
  2. 开始时间等于事件 y 开始时间且结束时间小于 y 结束时间的事件 x 必须首先出现在数组中。

然后，将 inActionEvent 设置为事件 0。遍历事件数组，并且对于不与 inActionEvent 重叠的每个事件 i 获得它们之间的空闲时间。每次检查 inActionEvent 和 i 事件之间的重叠后，如果它们不重叠，则将 inActionEvent 更改为 i 事件。如果它们重叠并且 i 结束时间大于 inActionEvent 结束时间，则将 inActionEvent 设置为 i 事件。否则保持 inActionEvent 原样（inActionEvent 可以在 i 事件之前开始并在我完成后结束，在这种情况下，您不要用 i 事件替换 inActionEvent）。

复杂性：O(n * lg n) 用于快速排序，O(n) 用于迭代 = O(nlgn)，有些人可能会说它是 O(n)

您的第一个解决方案需要 O(n*n) 最小值。

这意味着这个太快了。

示例代码：

inActionEvent = 0;
// dont forget to get free time form time 0 to start time of first event
for (int i=1;i<numberOfEvents;i++)
{
    if (!overlap(inActionEvent, i))
    {
        getFreeTimeBetweenThem(inActionEvent, i);
        inActionEvent = i;
    }
    else
    {
        if (events[inActionEvent].endtime<events[i].endtime)
            inActionEvent = i;
        else
            // do nothin
    }
}
// again dont forget to get free time from last event endtime to the end of day or something.
于 2013-09-24T12:02:07.093 回答