title: Algorithm to produce a difference of two collections of intervals
body: <h2>Problem</h2>
  
  <p>Suppose I have two collections of intervals, named A and B. How would I find a difference (a relative complement) in a most time- and memory-efficient way?</p>
  
  <p>Picture for illustration:
  <img src="https://i.stack.imgur.com/fj7bb.png" alt="enter image description here"></p>
  
  <p>Interval endpoints are <strong>integers</strong> ( ≤ 2<sup>128</sup>-1 ) and they are always both 2<sup>n</sup> long and aligned on the m×2<sup>n</sup> lattice (so you can make a binary tree out of them).</p>
  
  <p>Intervals can overlap in the input but this does not affect the output (the result if flattened would be the same).</p>
  
  <p>The problem is because there are MANY intervals in both collections (up to 100,000,000), so naïve implementations will probably be slow.</p>
  
  <p>The input is read from two files and it is sorted in such a way that smaller sub-intervals (if overlapping) come immediately after their parents in order of size. For example:</p>
  
  <pre><code>[0,7]
  [0,3]
  [4,7]
  [4,5]
  [8,15]
  ...
  </code></pre>
  
  <h2>What have I tried?</h2>
  
  <p>So far, I've been working on a implementation that generates a binary search tree while doing so aggregates neighbouring intervals ( <code>[0,3],[4,7] =&gt; [0,7]</code> ) from both collections, then traverses the second tree and "bumps out" the intervals that are present in both (subdividing the larger intervals in the first tree if necessary).</p>
  
  <p>While this appears to be working for small collections, it requires more and more RAM to hold the tree itself, not to mention the time it needs to complete the insertion and removal from the tree.</p>
  
  <p>I figured that since intervals come pre-sorted, I could use some dynamic algorithm and finish in one pass. I am not sure if this is possible, however.</p>
  
  <hr>
  
  <p>So, how would I go about solving this problem in a efficient way?</p>
  
  <p><strong>Disclaimer:</strong> This is not a homework but a modification/generalization of an actual real-life problem I am facing. I am programming in C++ but I can accept an algorithm in any [imperative] language.</p>