Find all intervals containing a given number

Question

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:

1. The list of intervals is long. (Might be 50K or more).
2. The intervals may be overlapping.
3. The list of interval does not change once we start querying.
4. 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.

Answer 1

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.