Python：動態區間數據結構

Question

我正在尋找一些python代碼來有效地計算區間重疊。 我以前使用過bx-python包的間隔樹，但現在需要從樹中刪除間隔（或者更好，修改它們）。 看來bx-python樹不支持這個。

任何指針？

謝謝。

Answer 1

可能存儲所有交叉點間隔可以提供幫助。

你需要：所有間隔的聯盟

• 界限，
• 從該交點作爲間隔中的每個路口左邊界和列表。

交叉區間可以存儲在樹中，因爲它們僅用左邊界表示。方法插入和刪除間隔看起來像（簡化）：

插入：找到新區間的左右邊界的交點區間，將這些交點區間拆分成2或3個新的交點區間。添加指針到新間隔之間的每個交點間隔。

刪除：查找左右邊界的交點區間，將它們合併到之前的交點區間。對於刪除指針刪除間隔之間的每個交點區間。

Answer 2

banyan支持從樹中刪除間隔。例如，爲了從時間間隔，例如一個列表中刪除時間間隔的最小數目的被留下的間隔不重疊在O(n log n)，banyan.SortedSet（增強紅黑樹）可以用於：

from banyan import SortedSet, OverlappingIntervalsUpdator # pip install banyan 

def maximize_nonoverlapping_count(intervals): 
    # build "interval" tree sorted by the end-point O(n log n) 
    tree = SortedSet(intervals, key=lambda (start, end): (end, (end - start)), 
        updator=OverlappingIntervalsUpdator) 
    result = [] 
    while tree: # until there are intervals left to consider 
     # pop the interval with the smallest end-point, keep it in the result 
     result.append(tree.pop()) # O(log n) 

     # remove intervals that overlap with the popped interval 
     overlapping_intervals = tree.overlap(result[-1]) # O(m log n) 
     tree -= overlapping_intervals # O(m log n) 
    return result 

示例：

print maximize_nonoverlapping_count([[3, 4], [5, 8], [0, 6], [1, 2]]) 
# -> [[1, 2], [3, 4], [5, 8]] 

請參閱Python - Removing overlapping lists。