algorithm - 寻找间隔

Question

我在 x 轴上有一组区间，我想找出包含某个元素的区间总数。我知道这个问题可以通过二分查找来解决，但我做不到。我该如何编码？(区间可能会重叠，不然我想到了用union find-disjoint set数据结构)

示例:

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

以上区间为实线区间(含)假设我有一个点向量:

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

如何继续我的二分搜索方法？

Answer 1

这是一个经典问题，可以通过扩充树来创建一个 Interval Tree 来解决。 .您基本上可以保持间隔的平衡树，其中键按递增的下端点排序，但每个节点在其子树中保留间隔的最高端点。

如果您在 Python 中执行此操作，我已经编写了一个程序包，Banyan , 支持这些查询。