交叉口範圍（算法）

Question

作爲例子，我有下一個數組：

[100,192] 
[235,280] 
[129,267] 

由於交叉陣列，我們得到：

[129,192] 
[235,267] 

簡單的練習的人，但問題創造算法找到第二multidim陣列...

任何語言，任何想法..

如果有人不understan ð我：

Answer 1

這是Python實現交集算法。其計算複雜度爲O（n^2）。

a = [[100,192],[235,280],[129,267]] 

def get_intersections(diapasons): 
    intersections = [] 
    for d in diapasons: 
     for check in diapasons: 
      if d == check: 
       continue 
      if d[0] >= check[0] and d[0] <= check[1]: 
       right = d[1] 
       if check[1] < d[1]: 
        right = check[1] 
       intersections.append([d[0], right]) 
    return intersections 

print get_intersections(a) 

Answer 2

我假設您希望輸出具有2個或更多重疊區間的任何範圍。
因此，[1,5],[2,4],[3,3]的輸出將是（僅）[2,4]。

這裏的基本想法是使用sweep-line algorithm。

將範圍拆分爲開始點和結束點。

對點進行排序。

現在通過與計數器變量初始化爲0

點迭代如果你得到一個起點：

• 增加計數器。
• 如果計數器的值現在爲2，則記錄該點作爲輸出中範圍的起點。

如果你得到一個終點

• 減少櫃檯。
• 如果計數器的值爲1，則記錄該點作爲輸出中範圍的終點。

注：

如果起點和終點具有相同的價值，你需要首先處理的終點，如果計數器爲1，起點首先如果計數器是2或更大，否則您將以輸出中兩個範圍之間的0尺寸範圍或0尺寸間隙結束。

這應該是相當簡單的通過具有一組下面的結構做：

Element 
    int startCount 
    int endCount 
    int value 

然後你把所有點以相同的值到一個這樣的元素，適當設置計數。

運行時間：

O(n log n)

實施例：

輸入：

[100, 192] 
[235, 280] 
[129, 267] 

（S爲開始，E對端）

Points | | 100 | 129 | 192 | 235 | 267 | 280 | 
Type | | Start | Start | End | Start | End | End | 
Count | 0 | 1 | 2 | 1 | 2 | 1 | 0 | 
Output | |  | [129, | 192] | [235, | 267] |  |