title: Possible Interview Question: How to Find All Overlapping Intervals
body: <p>It's not an interview question <em>per se</em>, as I came across this in my project, but I figured it could be a decent intervew question.</p>
  
  <p>You have N pairs of intervals, say integers.  You're required to indentify all intervals that overlap with each other in O(N) time. For example, if you have</p>
  
  <p>{1, 3}
  {12, 14}
  {2, 4}
  {13, 15}
  {5, 10}</p>
  
  <p>the answer is {1, 3}, {12, 14}, {2, 4}, {13, 15}. Note that you don't need to group them, so the result can be in any order like in the example.</p>
  
  <p>I just threw in O(N) time because the KMP algorithm takes O(N) for string search. :D</p>
  
  <p>The best I came up with and what I'm using right now in the project is O(N^2). Yeah, brute force is pretty sad, but no one complains so I won't refactor it. :P Still, I was curious if a greater mind has a more elegant solution.</p>