3
$\begingroup$

Given a set $S$ of $n$ overlapping intervals, where each interval is in the range of [1..O(n)], preprocess $S$ so we can efficiently answer the following query: Given an interval [i,j] output the interval from $S$ that has the longest overlap with [i,j] (i.e., their intersection is as large as possible). Note that [i,j] may or may not be one of the intervals in $S$.

It is relatively easy to get all overlapping intervals. You store an array Endpt[1..n] such that Endpt[t] equals the rightmost endpoint of all intervals in the set that begin at location t. You ask repeated Range-maximum queries on the range 1..j. As long as the answer is >j, you are getting an overlapping interval. This takes O(#answers) time since range-max is done in O(1) time.

The challenge of this question is that we want a more efficient way to find the interval with the longest overlap. To this end, we can consider 3 cases:

  1. intervals that begin before i
  2. intervals that end after j
  3. intervals that begin after i and end before j (i.e., that are contained within [i,j]).

For case 1, we can query Endpt array for range-max in the range 1..i-1 and find the longest overlapping interval of type 1 efficiently. Similarly, for case 2 we can store a Startpt array and query for range min.

Case 3 has me stumped. We could store a length array for all intervals, and ask for the range-max in i..j; however, this will not give the longest overlapping interval, since there will be intervals that begin after i and end after j. Is there a way to efficiently preprocess $S$ so that, given [i,j], we can efficiently find the longest interval contained within [i,j]? Or is there some other efficient way to solve the original problem?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Nice edit, and nice question! Thanks for all the additions -- this is a great improvement. Don't get too discouraged by the negative score (and that might change after folks see the edit). $\endgroup$
    – D.W. ♦
    Commented Jan 18, 2017 at 21:25
  • 1
    $\begingroup$ Perhaps there's a way to use a sweep line algorithm and a (partially) persistent tree data structure to solve this, though I don't immediately see how. Also, I assume you've looked at segment trees and interval trees? $\endgroup$
    – D.W. ♦
    Commented Jan 18, 2017 at 21:40

1 Answer 1

Reset to default
3
$\begingroup$

You're just a step away from the answer.

Delete all intervals in $S$ which are contained in another interval in $S$. Now $S$ is totally ordered, i.e. for any two interval $[l,r]$ and $[l',r']$, either $l<l'$ and $r<r'$ or $l>l'$ and $r>r'$. Now it's not hard to find the first interval $[l,r]$ s.t. $l\ge i$ and the last interval $[l',r']$ s.t. $r'\le j$, and a range-max of length array on the interval $[l, l']$ gives you the answer.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Nice. I also wanted to be able to remove the longest interval and query again for second longest overlap etc. I suppose we can keep the removed intervals in a tree (root is 1..n, and each child is a sub-interval of parent) and then add back children intervals when a parent is removed. $\endgroup$
    – user64724
    Commented Jan 20, 2017 at 2:57
  • $\begingroup$ @user64724 The problem is that's not a tree since an interval can be contained in multiple intervals. For example, both $[l,r]$ and $[l',r']$ contain $[l',r]$. I think it's still possible to remove one interval and update $S$ but it might require more effort. $\endgroup$
    – aaaaajack
    Commented Jan 20, 2017 at 5:05
  • $\begingroup$ Another option if several answers are needed: Check whether any interval overlaps full [i,j]. A range max on 1..i gives answer. If not, check if any overlaps half. 2 range max queries give the answer. Proceed by dividing interval into half with time O(log j-i). Answers are not necessarily found in sorted order, but can easily be put in order. $\endgroup$
    – user64724
    Commented Jan 20, 2017 at 16:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.