title: search for interval overlap in list of intervals?
body: <p>Say [a,b] represents the interval on the real line from a to b, a &lt; b, inclusive (ie, [a,b] = set of all x such that a&lt;=x&lt;=b).  Also, say [a,b] and [c,d] are 'overlapping' if they share any x such that x is in both [a,b] and [c,d].  </p>
  
  <p>Given a list of intervals, ([x1,y1],[x2,y2],...), what is the most efficient way to find all such intervals that overlap with [x,y]?</p>
  
  <p>Obviously, I can try each and get it in O(n).  But I was wondering if I could sort the list of intervals in some clever way, I could find /one/ overlapping item in O(log N) via a binary search, and then 'look around' from that position in the list to find all overlapping intervals.  However, how do I sort intervals such that such a strategy would work?  </p>
  
  <p>Note that there may be overlaps between elements in the list items itself, which is what makes this hard.</p>
  
  <p>I've tried it by sorting intervals by their left end, right end, middle, but none seem to lead to an exhaustive search.</p>
  
  <p>Help?</p>