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:
- intervals that begin before i
- intervals that end after j
- 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?