title: Range intersection / union
body: <p>I'm developing a programming language for which I want to provide a <strong>Range</strong> data type which for now is, not as usually, a list of pairs of <code>int</code> values <code>(x,y)</code> with the constraint that <code>x &lt; y</code>. I say not as usually because usually a range is just a pair but in my case it is more than than, allowing to have for example</p>
  
  <pre><code>1 to 5, 7 to 11, 13 to 22
  </code></pre>
  
  <p>all contained in a single object.</p>
  
  <p>I would like to provide two functions to generate the union and the instersection of two ranges, that should contain the least number of non-overlapping intervals from a couple of ranges.. so for example</p>
  
  <pre><code>1 to 5 || 3 to 8 = 1 to 8
  1 to 5 &amp;&amp; 3 to 8 = 3 to 5
  (1 to 3, 4 to 8) &amp;&amp; 2 to 6 = (2 to 3, 4 to 6)
  </code></pre>
  
  <p>where <code>||</code> is union and <code>&amp;&amp;</code> is intersection.</p>
  
  <p>For now their implementation is, as stated before, just a list.. I know that a more suitable data structure exists (interval tree) but for now I'm more concerned in building new lists from the union/intersection of other lists..</p>
  
  <p>Which are the state-of-the-art algorithms to implement these two functions?</p>
  
  <p>Thanks in advance</p>