算法陣列

Question

我有一個包含n個間隔[0,1]

每個間隔看起來像[a(i),b(i)] 0<=a(i)<b(i)<=1 , i = 1...n

我需要找到一種有效的算法中確定每個n個間隔的，如果它的內部包含一個列表內發現間隔其他區間。

我試過很多選擇，但我只能找到一個在爲O（n^2）

有什麼建議？

Answer 1

提示：對列表進行排序。

Answer 2

假設只有一個區間[0,1]。如果它不在列表中，只是爲了方便而添加它。

排序端點。在兩個端點相同的情況下，在相應的右端點上反向排序它們。因此[0.1,0.2]，[0.1,0.3]將被排序爲0.1,0.1,0.2,0.3，其中第一個0.1以第二間隔進行。同樣如果右端點是相等的。

每個端點都應該有一個對其間隔的引用，以便您可以找到給定端點的時間間隔。

掃描排序的端點。和你一樣，建立一棵樹。使用[0,1]作爲根。節點可能是紅色或綠色。他們從紅色開始。所以根節點最初是紅色的。

樹的想法是，如果一個區間包含另一個區間，那麼它最終將成爲樹中的祖先。如果兩個區間不重疊或部分重疊，它們將位於不同的分支中，並且它們唯一的共同祖先將是根，或者包含它們的其他區間。

當遇到每個左端點時，通過向其當前樹節點添加一個紅色節點作爲其間隔，將其添加到樹中的臨時位置。因此，我們遇到的第一個端點會導致相應的時間間隔被添加到根目錄下，併成爲當前節點。因此，在遇到右手端點之前，樹節點可能會連接多個節點。

當遇到右手端點時，其節點變爲綠色，因爲我們已經從一端到另一端完全覆蓋了它。如果它有任何紅色的後代，它們必須被移動，因爲當正好轉向的綠色節點包含它們的左端時，它不包含它們的右端。所以我們把它們全部移到父節點（它仍然是紅色的）。

我們繼續這個過程，直到我們到達1.0端點。此時樹完成。所有節點都是綠色的。每個節點下的節點表示對應的時間間隔包含的時間間隔。

Answer 3

1. 排序根據自己的起點打破關係，使得早期的端點出現後
2. 觀察到，在排定的順序，每一個元素E的間隔，含值e只能存在於它的左邊。
3. 因此從左側線性掃描到目前觀察到的最大終點的軌跡。在任何階段，如果當前時間間隔的終點小於最大終點，我們發現一個包含在另一個時間間隔內的時間間隔。