algorithm - Finding the interval

Question

I have a set of intervals on the x-axis and i wish to find out the total number of intervals containing a certain element. I know that the problem can be solved by binary search but am not able to do so. How do I code it up? (the intervals may overlap, otherwise I thought of using union find-disjoint set data structure)

Example :

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

The above intervals are the intervals on the real line.(inclusive) and suppose I have a vector of points:

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

How do I proceed with my binary search approach?

Answer 1

这是一个经典问题，可以通过增加树来创建区间树来解决。您基本上可以保持一个平衡的区间树，其中键按增加的较低端点排序，但每个节点在其子树中保留区间的最高端点。

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