查找間隔

Question

我在x軸上有一組間隔，我希望找出包含某個元素的間隔的總數。我知道這個問題可以通過二分查找來解決，但我們無法做到。我如何編碼？ （間隔可重疊，否則我想用聯合找到不相交的集合的數據結構的）

例：

Intervals : 
(1,10) 
(2,12) 
(4,9) 
(3,7) 
(5,15) 

上述間隔是在實線的間隔（含） ，並假設我有一個向量點：

v=[2,5,6,7,1,3] 

如何繼續我的二進制搜索方法？

Answer 1

這是一個典型的問題，可以通過擴充來解決，以創建一個Interval Tree。您基本上可以保持一個平衡的間隔樹，其中按照增加的較低端點對鍵進行排序，但每個節點都保留子樹中間隔的最高端點。

如果你在Python中這樣做，我寫了一個包，Banyan，支持這些查詢。