Finding longest overlapping interval pair

Question

Say I have a list of n integral intervals [a,b] each representing set S = {a, a+1, ...b}. An overlap is defined as |S_1 \cap S_2|. Example: [3,6] and [5,9] overlap on [5,6] so the length of that is 2. The task is to find two intervals with the longest overlap in Little-O(n^2) using just recursion and not dynamic programming.

Naive approach is obviously brute force, which does not hold with time complexity condition. I was also unsuccessful trying sweep line algo and/or Longest common subsequence algorithm.

I just cannot find a way of dividing it into subproblems. Any ideas would be appreciated.

Also found this, which in my opinion does not work at all:

Finding “maximum” overlapping interval pair in O(nlog(n))

Answer 1

Here is an approach that takes N log(N) time.

Breakdown every interval [a,b] [c,d] into an array of pair like this:

pair<a,-1>
pair<b,a>
pair<c,-1>
pair<d,c>

sort these pairs in increasing order. Since interval starts are marked as -1, in case of ties interval they should come ahead of interval ends.

for i = 0 to end of the pair array
    if current pair represents interval start
        put it in a multiset
    else
        remove the interval start corresponding to this interval end from the multiset.
        if the multiset is not empty
            update the maxOverlap with (current_interval_end - max(minimum_value_in_multiset,start_value_of_current_interval)+1)

This approach should update the maxOverlap to the highest possible value.