最有效的方法來重疊範圍？

我有一個內存中的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

最有效的方法來重疊範圍？

回答

相關問題