從間隔列表中有效查找重疊間隔

這與查找重疊間隔有關。我知道如何給定一個間隔列表（間隔樹）。我所擁有的是間隔列表。例如，從間隔列表中有效查找重疊間隔

[2,6], [7,11] 
[1,3], [5,10], [11,13] 
[2,5], [6,8]

這個結果應該是

[2,3]，[7,8]

我需要做的是找到所有列表中常見的間隔列表。

我看到此問題與合併n列表類似。問題是我無法應用列表的成對合並。應用此方法會導致重疊間隔的丟失。所以我需要將所有列表合併在一起考慮所有列表（而不是成對）。

我可以使用區間樹。將每個列表的第一個區間插入到區間樹中並找到重疊區域。從樹中刪除最薄弱的時間間隔，並從其中一個列表中插入下一個時間間隔。我還沒有完全想到如何使用這種方法，但似乎它會變得太昂貴。

是否有任何有效的算法來從間隔列表中查找重疊間隔。

附加信息： 列表中的間隔進行排序。它們不重疊並形成一個序列。

來源

2013-08-22 akaHuman

創建單個排序的轉換數組。根據您加入或離開的時間間隔，每個轉場都有一個位置和一個累計數字。當你通過列表時，記住你有多少個間隔。當你處於一系列的間隔時，就是你處於一個常見的間隔時間。

對於示例的過渡將是：

[2, 1], [6, -1], [7, 1], [11, -1], 
[1, 1], [3, -1], [5, 1], [10, -1], [11, 1], [13, -1] 
[2, 1], [5, -1], [6, 1], [8, -1]

其按位置排序和合並崩潰後：

[1, 1], [2, 2], [3, -1], [5, 0], [6, 0], [7, 1], [8, -1], [10, -1], [11, 0], [13, -1]

，讓你轉換運行的總計：

[1, 1], [2, 3], [3, 2], [7, 3], [8, 2], [10, 2], [13, 1]

然後我們可以讀取我們在3的時間間隔，從一開始2並且去到3，另一個從7開始並且去到8。這是答案。

創建一個長列表和排序的想法無疑是額外的工作。您可以創建這些列表並將它們即時合併。節省量是系列數量的日誌的一個因素，而不是事件數量的日誌。

來源

2013-08-22 07:38:46 btilly

很抱歉，我失去了你在「這給你跑轉總數」。你能否詳細說明一下。謝謝！ – akaHuman

第一個條目仍然是位置。第二個是這一點的變化總和。所以我們開始'[1,1]'，然後'[2,1 + 2]'，然後'[2,1 + 2-1]'等等（因爲變化遵循'1,2，-1， 0，0，1，-1，-1,0，-1'）。 0轉換並不重要，所以我放棄了它們。 – btilly

謝謝！這是一個很好的。 – akaHuman

我對你想要做什麼的理解是在區間列表上應用交集操作。你可以做成這樣兩兩交叉是相關聯的。

我會做的是一樣的東西

Let S be the set of sets, R = s1, s1 in S 
    for each set s2 in S/{s1} 
       for each element e1 in R 
        for each element e2 in s2 s.t. e1.sup < e2.inf 
        e1 <- intersection (e1, e2)

兩個間隔之間的交集操作

intersection (e1,e2): 
    return new Interval(max(e1.inf, e2.inf), min (e1.sup, e2.sup));

來源

2013-08-22 07:56:05 hpid91

這是我猜的蠻力解決方案！如果我能找到一個更高效的解決方案，我期待着。 – akaHuman

是的，它是O（n）。如果你的集合是有序的，那麼你可以在平均情況下做得更好（當你遇到一個元素e2，只要第二個元素的下界優先於第二個元素的上界就可以跳出第二個循環，只需編輯僞代碼即可。 – hpid91

你說的間隔中的每個單獨的列表進行排序和非重疊。所以，

Keep track of where you are in each list, starting at the beginning of each. 
While none of the lists has run out: 
    If the current intervals (one from each list) all overlap: 
     Output the intersection of the current intervals 
    Find which of the current intervals has the earliest end point 
    Advance one position within that list.

如果有時間間隔和N個區間共K個清單，如果以最簡單的方式實現，但是你應該能夠將這一數字減少至O應該採取O（NK）時間（N日誌K）時間，方法是跟蹤有關堆或其他優先級隊列中當前時間間隔的信息。

來源

2013-08-22 15:31:06

從間隔列表中有效查找重疊間隔

回答

相關問題