title: Finding "maximum" overlapping interval pair in O(nlog(n))
body: <p><strong>Problem Statement</strong></p>
  
  <p><strong>Input</strong>
  set of n intervals; {[s_1,t_1], [s_2,t_2], ... ,[s_n,t_n]}.</p>
  
  <p><strong>Output</strong>
  pair of intervals; {[s_i,t_i],[s_j,t_j]}, with the <em>maximum</em> overlap among all the interval pairs.</p>
  
  <p><strong>Example</strong></p>
  
  <p>input intervals : {[1, 10], [2, 6], [3,15], [5, 9]}</p>
  
  <p>-> There are possible 6 interval pairs. Among those pairs, [1,10] &amp; [3,15] has the largest possible overlap of 7.</p>
  
  <p>output : {[1,10],[3,15]}</p>
  
  <p>A naive algorithm will be a brute force method where all n intervals get compared to each other, while the current maximum overlap value being tracked. The time complexity would be O(n^2) for this case.</p>
  
  <p>I was able to find many procedures regarding <em>interval trees</em>, <em>maximum number of overlapping intervals</em> and <em>maximum set of non-overlapping intervals</em>, but nothing on this problem. Maybe I would be able to use the ideas given in the above algorithms, but I wasn't able to come up with one. </p>
  
  <p>I spent many hours trying to figure out a nice solution, but I think I need some help at this point. </p>
  
  <p>Any suggestions will help!</p>