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?
This is a classic problem which can be solved via augmentation of a tree to create an Interval Tree. You can basically hold a balanced tree of intervals, where the keys are sorted by increasing lower endpoint, but each node keeps the highest endpoint of the intervals in its subtree.
In case you're doing this in Python, I've written a package, Banyan, that supports these queries.