title: Computing the smallest positive integer not covered by any of a set of intervals
body: <p>Someone posted this question here a few weeks ago, but it looked awfully like homework without prior research, and the OP promptly removed it after getting a few downvotes.</p>
  
  <p>The question itself was rather interesting though, and I've been thinking about it for a week without finding a satisfying solution. Hopefully someone can help?</p>
  
  <p>The question is as follows: <strong>given a list of N integer intervals, whose bounds can take any values from <code>0</code> to <code>N³</code>, find the smallest integer <code>i</code> such that <code>i</code> does not belong to any of the input intervals.</strong></p>
  
  <p>For example, if given the list <code>[3,5] [2,8] [0,3] [10,13]</code> (N = 4) , the algorithm should return <code>9</code>.</p>
  
  <p>The simplest solution that I can think of runs in <code>O(n log(n))</code>, and consists of three steps:</p>
  
  <ol>
  <li>Sort the intervals by increasing lower bound</li>
  <li><ul>
  <li>If the smallest lower bound is > 0, return 0; </li>
  <li>Otherwise repeatedly merge the first interval with the second, until the first interval (say <code>[a, b]</code>) does not touch the second (say <code>[c, d]</code>) — that is, until b + 1 &lt; c, or until there is only one interval.</li>
  </ul></li>
  <li>Return <code>b + 1</code></li>
  </ol>
  
  <p><strong>This simple solution runs in <code>O(n log(n))</code>, but the original poster wrote that the algorithm should run in <code>O(n)</code>.</strong> That's trivial if the intervals are already sorted, but the example that the OP gave included unsorted intervals. <strong>I guess it must have something to do with the <code>N³</code> bound</strong>, but I'm not sure what... Hashing? Linear time sorting? Ideas are welcome.</p>
  
  <hr>
  
  <p>Here is a rough python implementation for the algorithm described above:</p>
  
  <pre><code>def merge(first, second):
      (a, b), (c, d) = first, second
      if c &lt;= b + 1:
          return (a, max(b, d))
      else:
          return False
  
  def smallest_available_integer(intervals):
      # Sort in reverse order so that push/pop operations are fast
      intervals.sort(reverse = True)
  
      if (intervals == [] or intervals[-1][0] &gt; 0):
          return 0
  
      while len(intervals) &gt; 1:
          first = intervals.pop()
          second = intervals.pop()
  
          merged = merge(first, second)
          if merged:
              print("Merged", first, "with", second, " -&gt; ", merged)
              intervals.append(merged)
          else:
              print(first, "cannot be merged with", second)
              return first[1] + 1
  
  print(smallest_available_integer([(3,5), (2,8), (0,3), (10,13)]))
  </code></pre>
  
  <p>Output:</p>
  
  <pre><code>Merged (0, 3) with (2, 8)  -&gt;  (0, 8)
  Merged (0, 8) with (3, 5)  -&gt;  (0, 8)
  (0, 8) cannot be merged with (10, 13)
  9
  </code></pre>