Find all intervals containing a given number
algorithm, data-structures
Solution
This is a well-defined problem that is most efficiently solved using an interval tree (see wikipedia, here and here) for an explanation.
I wouldn't recommend a hash table since for configurations with a lot of overlap you may end up storing O(n) segments per entry, requiring O(n^2) storage total.
Problem
I have a list of intervals which might be overlapping. And, then I have a value and the problem is to find all the intervals which contain that value, the value itself being inclusive. I have seen several approaches including range trees, KD trees etc. But, I am wondering if there is a specific optimized solution for this problem, considering: - The list of intervals is long. (Might be 50K or more). - The intervals may be overlapping. - The list of interval does not change once we start querying. - The list once formed, is queried for a large number of times with different values. Could someone suggest some approaches to solve this. Thanks in advance.