# Finding the longest overlapping interval pair

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.

• stackoverflow.com/questions/39312714/… Maybe one can quote the answer there? Apr 12 '18 at 6:55
• @xskxzr that one is just wrong. Not correct at all. Apr 12 '18 at 7:11
• I didn't check that answer carefully. If you find it's wrong, what about leaving a comment? Apr 12 '18 at 7:19
• Must you use recursion? Sweep line algorithm does not use recursion. Apr 13 '18 at 3:47
• @AndrejKováč: Your claim that the solution xskxzr linked to is "just wrong" is not only itself wrong, but unhelpful and lazy. I suggest trying to give a counterexample to its correctness, and letting that guide you to a proof that it is in fact correct. Jun 12 '18 at 10:42