找到重疊項目的所有獨特組合？

如果我有在一個元組列表的形式數據：找到重疊項目的所有獨特組合？

[(uid, start_time, end_time)]

我想找到在時間上重疊的UID的所有獨特的組合。例如，如果我有類似下面的列表：

[(0, 1, 2), 
(1, 1.1, 3), 
(2, 1.5, 2.5), 
(3, 2.5, 4), 
(4, 4, 5)]

我想獲得的輸出：

[(0,1,2), (1,3), (0,), (1,), (2,), (3,), (4,)]

是否有這種更快的算法比天真蠻力？

來源

2016-03-01 Sean McAllister

無視我的意見。我以爲你試圖找到所有的對，而不是所有的組合。儘管如此，您仍然可以應用掃描線算法的相同想法：對所有時間進行排序並遍歷它們，同時保留一組當前覆蓋的時間間隔（uid）。每當你達到一個新的點時，你將刪除所有沒有覆蓋的間隔，並建立當前組+當前時間的所有組合。然後將該uid添加到該集合並繼續。 – ale64bit

首先，按開始時間對你的元組進行排序。保存一堆活躍的元組，其中包含最早結束時間最早的元組。

然後，您將遍歷已排序的列表並將元組添加到活動集。這樣做，你也檢查是否需要刪除元組。如果是這樣，你可以報告一個時間間隔。爲了避免重複報告，只有在自上一次報告以來已將新元組添加到活動集中時才報告新的時間間隔。

下面是一些僞代碼，可視化的想法：

sort(tuples) 
activeTuples := new Heap 
bool newInsertAfterLastReport = false 
for each tuple in tuples 
    while activeTuples is not empty and activeTuples.top.endTime <= tuple.startTime 
     //the first tuple from the active set has to be removed 
     if newInsertAfterLastReport 
      report activeTuples 
      newInsertAfterLastReport = false 
     activeTuples.pop() 
    end while 
    activeTuples.insert(tuple) 
    newInsertAfterLastReport = true 
next 
if activeTuples has more than 1 entry 
    report activeTuples

與您的示例數據集中您將獲得：

data = [(0, 1, 2), (1, 1.1, 3), (2, 1.5, 2.5), (3, 2.5, 4), (4, 4, 5)] 

tuple   activeTuples    newInsertAfterLastReport 
--------------------------------------------------------------------- 
(0, 1, 2)  []          false 
       [(0, 1, 2)]        true 
(1, 1.1, 3)  
       [(0, 1, 2), (1, 1.1, 3)] 
(2, 1.5, 2.5) 
       [(0, 1, 2), (2, 1.5, 2.5), (1, 1.1, 3)] 
(3, 2.5, 4)  -> report (0, 1, 2) 
       [(2, 1.5, 2.5), (1, 1.1, 3)]    false 
       [(1, 1.1, 3)]        
       [(1, 1.1, 3), (3, 2.5, 4)]    true 
(4, 4, 5)  -> report (1, 3)       false 
       [(3, 2.5, 4)] 
       [] 
       [(4, 4, 5)]

事實上，我會刪除if activeTuples has more than 1 entry一部分，總是在報告結束。這將導致額外的報告(4)，因爲它不包含在任何以前的報告（而(0) ... (3)是）。

來源

2016-03-01 18:22:18

我認爲這可以在O（n lg n + n o）時間內完成，其中o是您的輸出的最大尺寸（在最壞的情況下o可能是n）。爲每個start_time或end_time構建一個3元組，如下所示：第一個組件是輸入元組的start_time或end_time，第二個組件是輸入元組的id，第三個組件是start_time或end_time。現在你有2n 3元組。按照第一個組件的升序對它們進行排序。現在開始掃描從最小到最大的3元組列表。每次開始範圍時，將其id添加到平衡二叉搜索樹（在O（lg o）時間）中，並輸出樹的內容（在O（o）中），並且每次範圍結束時，將其id從樹（在O（lg o）時間）。您還需要照顧角落的情況，例如，如何處理相同範圍或不同範圍的相同開始和結束時間。

來源

2016-03-01 18:20:11

找到重疊項目的所有獨特組合？

回答

相關問題