algorithm search data-structures tree intervals

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

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.

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 $O(sqrt(n)+k)$ or $O(log^2+n +k)$ runtime, where k is the number of points reported.