All geek questions in one place

Find all intervals containing a given number

I have a list of intervals that may overlap. And then I have a value, and the problem is to find all the intervals that contain this value, and the value itself is 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, given:

  • The list of intervals is long. (Maybe 50K or more).
  • Intervals may overlap.
  • The list of intervals does not change after the start of the request.
  • The list that was generated is queried for a large number of times with different values.

Can someone suggest some approaches to solve this. Thanks in advance.

+4
source share
2 answers

This is a well-defined problem that is most effectively solved using the interval tree (see wikipedia , here and here ) for an explanation.

I would not recommend a hash table, since for configurations with a large number of overlaps, you can end up saving O (n) segments for writing, requiring a total storage capacity of O (n ^ 2).

+6
source

If you do not mind the expensive initialization time, you can use any of the methods you described to pre-calculate the intervals for all the corresponding values ​​that you can meet at the request stage, limited by the minimum and maximum values.

Create a hash table with these results, and you can find all the intervals for the given value in O (1).

+1
source

Source: https://habr.com/ru/post/1446646/

More articles:


All Articles