Fast Data Structure For Point Interval Lookups

Question

I have an interesting problem I'm working on right now and wonder if anyone has had success in implementing high performance solutions to it.

I have a set of "intervals" meaning an array of arrays each of the form

Intervals = [
     [min_val_1, max_val_1],
     [min_val_2, max_val_2],
     ...
     [min_val_n, max_val_n]
]

Where all these values are real valued. Now I have a number and I want to ask, which intervals contain this numbers? And I need to be able to answer this very quickly. I can preprocess as much as needed and space is less of a consideration than time. What approach would you recommend? Thanks in advance!

Answer 1

I recommend using an interval tree