Say I have a list of $n$ integral intervals $[a,b]$ where each represents a set $S = \{a, a+1, \ldots, 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 $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.