CODEWITHSUNDEEP
algorithmsearchdata-structurestreeintervals
Steve M
Steve M

Reputation: 83

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.

Upvotes: 5

Views: 1740

Answers (2)

Thomas B.
Thomas B.

Reputation: 2296

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.

range query

Upvotes: 5

Evgeny Kluev
Evgeny Kluev

Reputation: 24677

Persistent binary search tree may be used here.

Pre-processing:

  1. Create empty persistent tree. It should store intervals sorted by their ending points.
  2. Sort intervals by their starting points.
  3. For each interval, starting from the end of sorted list, create a "copy" of persistent tree and add this interval to this copy.

Search:

  1. Find starting point of the query interval in sorted list.
  2. Iterate corresponding "copy" of persistent tree from the smallest key to end of the query interval.

Search time complexity is O(log(n) + m), where m is number of elements in the output.

Upvotes: 1

Related Questions