Given an interval, Find all intervals In a list of Intervals

Question

Let say I have a list of ranges like this

[[1,3], [2,5], [4,6], [8,10], [12,15], [13,17]]

Now I want to find a range say [3,11] falls in. My algorithm should give me all the ranges this range falls to. For example the output for this should be

Output - [1,3], [2,5], [4,6], [8,10]

How do i go about solving this?

PS: I know segment tree might be helpful. Where I can build the tree to store interval and query a Point lying inside interval, but how to get all intervals given a interval.

Answer 1

Interval Tree is definitely the data structure you need. I faced the same problem and in order to improve performances I used Augmented Interval Tree where every node includes, in addition to the bounds of the range, also the information related to the maximum value of the subtree of the node.

You can find here an in depth explanation and a Java implementation: Data Structures: Augmented Interval Tree to search for intervals overlapping