1
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ stackoverflow.com/questions/39312714/… Maybe one can quote the answer there? $\endgroup$ – xskxzr Apr 12 '18 at 6:55
  • $\begingroup$ @xskxzr that one is just wrong. Not correct at all. $\endgroup$ – Andrej Kováč Apr 12 '18 at 7:11
  • 1
    $\begingroup$ I didn't check that answer carefully. If you find it's wrong, what about leaving a comment? $\endgroup$ – xskxzr Apr 12 '18 at 7:19
  • $\begingroup$ Must you use recursion? Sweep line algorithm does not use recursion. $\endgroup$ – xskxzr Apr 13 '18 at 3:47
  • 1
    $\begingroup$ @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. $\endgroup$ – j_random_hacker Jun 12 '18 at 10:42
1
$\begingroup$

Hint: Try divide-and-conquer. I can only see about two plausible ways to do the "divide" step; try both of them, and one of them should work to yield a useful algorithm.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.