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:


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?
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&lt;l'$ and $r&lt;r'$ or $l&gt;l'$ and $r&gt;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.