# Find longest overlapping interval

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?

• 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). – D.W. Jan 18 '17 at 21:25
• 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? – D.W. Jan 18 '17 at 21:40

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.

• 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. – user64724 Jan 20 '17 at 2:57
• @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. – aaaaajack Jan 20 '17 at 5:05
• 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. – user64724 Jan 20 '17 at 16:50