寻找间隔
Finding the interval
我在 x 轴上有一组区间，我想找出包含某个元素的区间总数。我知道这个问题可以通过二分查找来解决，但我做不到。我该如何编码？
（区间可能会重叠，不然我想到了用union find-disjoint set数据结构）
示例：
Intervals :
(1,10)
(2,12)
(4,9)
(3,7)
(5,15)
以上区间为实线区间（含）
假设我有一个点向量：
v=[2,5,6,7,1,3]
如何继续我的二进制搜索方法？
这是一个经典问题，可以通过 扩充 树来创建 Interval Tree 来解决。您基本上可以保持间隔的平衡树，其中键按递增的下端点排序，但每个节点在其子树中保留间隔的最高端点。
如果您在 Python 中执行此操作，我已经编写了一个支持这些查询的程序包 Banyan。
我在 x 轴上有一组区间，我想找出包含某个元素的区间总数。我知道这个问题可以通过二分查找来解决，但我做不到。我该如何编码？ （区间可能会重叠，不然我想到了用union find-disjoint set数据结构）
示例：
Intervals :
(1,10)
(2,12)
(4,9)
(3,7)
(5,15)
以上区间为实线区间（含） 假设我有一个点向量：
v=[2,5,6,7,1,3]
如何继续我的二进制搜索方法？
这是一个经典问题，可以通过 扩充 树来创建 Interval Tree 来解决。您基本上可以保持间隔的平衡树，其中键按递增的下端点排序，但每个节点在其子树中保留间隔的最高端点。
如果您在 Python 中执行此操作，我已经编写了一个支持这些查询的程序包 Banyan。