title: Intersection of two lists of ranges in Python
body: <p>A friend of mine passed me over an interview question he recently got and I wasn't very happy with my approach to the solution. The question is as follows:</p>
  
  <ul>
  <li>You have two lists. </li>
  <li>Each list will contain lists of length 2, which represent a range (ie. [3,5] means a range from 3 to 5, inclusive). </li>
  <li>You need to return the intersection of all ranges between the sets. If I give you [1,5] and [0,2], the result would be [1,2]. </li>
  <li>Within each list, the ranges will always increase and never overlap (i.e. it will be [[0, 2], [5, 10] ... ] never [[0,2], [2,5] ... ])</li>
  </ul>
  
  <p>In general there are no "gotchas" in terms of the ordering or overlapping of the lists.</p>
  
  <p>Example:</p>
  
  <pre><code>a = [[0, 2], [5, 10], [13, 23], [24, 25]]
  b = [[1, 5], [8, 12], [15, 18], [20, 24]]
  </code></pre>
  
  <p>Expected output:
      <code>[[1, 2], [5, 5], [8, 10], [15, 18], [20, 24]]</code></p>
  
  <p>My lazy solution involved spreading the list of ranges into a list of integers then doing a set intersection, like this:</p>
  
  <pre><code>def get_intersection(x, y):
      x_spread = [item for sublist in [list(range(l[0],l[1]+1)) for l in x] for item in sublist]
      y_spread = [item for sublist in [list(range(l[0],l[1]+1)) for l in y] for item in sublist]
      flat_intersect_list = list(set(x_spread).intersection(y_spread))
  ...
  </code></pre>
  
  <p>But I imagine there's a solution that's both readable and more efficient.</p>
  
  <p>Please explain how you would mentally tackle this problem, if you don't mind. A time/space complexity analysis would also be helpful.</p>
  
  <p>Thanks</p>