最有效的方法来重叠范围？

我有一个内存中的List<Event>，它可以是长度从1到50000+的任何值（不理想，但情况是）。每个Event包含一个openTime属性和一个closedTime属性，它们被存储为Long。最有效的方法来重叠范围？

鉴于事件可能重叠，我需要确定事件处于活动状态的时间量。当你用图形来看它并不是很困难。

enter image description here

我实现了几种解决方案，但我发现它很难找到不有显著时间资源影响的解决方案！我目前的解决方案包括

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

这些都不是性能友好的，所以任何有效的方式来实现这一点的建议将非常赞赏？

来源

2013-09-24 tarka

课堂活动 int start，end; }

使用快速排序的事件如下排序：

事件X与启动时间小于事件是开始时间必须在阵列第一次出现。
事件x的开始时间等于事件y的开始时间，结束时间小于y结束时间必须首先出现在数组中。

然后，inActionEvent设置为0事件迭代事件的阵列上和每一个事件我认为不与inActionEvent重叠，得到它们之间的自由时间。每次在检查inActionEvent和i事件之间的重叠之后，如果它们不重叠，请将inActionEvent更改为i事件。如果它们重叠，并且结束时间大于inActionEvent结束时间，则将inActionEvent设置为i事件。否则保持inActionEvent（inActionEvent可以在我的事件之前开始，并在我完成后结束，在这种情况下，您不会用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-24 12:02:07 hasan83

人们为什么害羞投票给我！ – hasan83

这比我的方法更好，并导致我失去了一些好主意。我并不完全相信这是最有效率的，所以我只是暂时将其标记为正确的答案。 – tarka

我不认为这样的问题可以通过更少的O（nlgn）和定义来解决。你可以稍微等一下，但是你会发现比nlgn更好。而且很实用。 – hasan83

最有效的方法来重叠范围？

回答

相关问题