title: Finding elementary intervals in overlapping intervals
body: <p>I came across a good question while preparing for some programming interviews.</p>
  
  <p>Given a set of possibly overlapping intervals, you need to write a function to return all elementary intervals among them. For example: if you are given intervals as the following list of pairs: {{1,5}, {3,10}, {5,11}, {15,18}, {16,20}}, then you need to return the following:</p>
  
  <p>{{1,3}, {3,5}, {5,10}, {10,11}, {15,16}, {16,18}, {18,20}}</p>
  
  <p>Note the following in the above answer:</p>
  
  <ul>
  <li>The interval {11,15} is omitted in the answer because it is
  non-existent in the input.</li>
  <li>The interval {1,5} from the input has been split up into {1,3}, {3,5}
  in the answer because of the starting point "3" defined in {3,10} in
  the input that cuts the interval into    two elementary intervals.</li>
  </ul>
  
  <p>Method signature in Java:</p>
  
  <pre class="lang-java prettyprint-override"><code>List&lt;Pair&lt;Integer, Integer&gt;&gt; generateElementaryIntervals(List&lt;Pair&lt;Integer, Integer&gt; intervals)
  </code></pre>
  
  <p>One of the solutions that I imagined was to separate the input into non-intersecting sets, and then a simple O(NlogN) sort over all numbers in each non-intersecting set will yield the answer. Is there a more efficient way to do it? </p>