You are given a set of intervals S. You have to find all intervals in S that are contained in a given interval (a, b) in minimum time complexity
algorithm, data-structures, intervals, search, tree
Solution
You can remodel your problem in the 2D-plane. Let the `(begin, end)` of each interval be a two-dimensional point. (Note that all valid intervals will end up above the diagonal)
Your Interval-search-problem transforms into well-studied orthogonal 2D range queries with algorithms that have or runtime, where k is the number of points reported.
Problem
You are given a set of intervals `S`. You have to find all intervals in `S` that are contained in a given interval `(a, b)` in minimum time complexity. This can be done in `O(n)` time by brute force, where `n` is the number of intervals in set `S`. But if I am allowed to do some pre-processing, can this be done in less than `O(n)` time e.g. `O(log n)` time? Initially I was thinking of interval tree, but I don't think it is applicable here because interval tree is used to get all intervals that overlaps with a given interval.