title: Intervals to non-overlapping subintervals
body: <p>I'm trying to divide a list of intervals into non-overlapping subintervals. For example, if my input were</p>
  
  <pre><code>[1,5],[4,9],[6,12],[11,17]
  </code></pre>
  
  <p>I would want the output to be</p>
  
  <pre><code>[1,4], [4,5], [5,6], [6,9], [9,11], [11,12], [12,17]
  </code></pre>
  
  <p>I want the output to be a list of intervals that has the same union as the original list of intervals but where every overlapping sub-interval of multiple different subintervals is made into a different interval. </p>
  
  <p>My first thought is that I should sort all intervals by their first element, and if there is an overlap I should create a new interval, but I've been having some trouble getting this to work. This seems different in nature than many interval problems, so any suggestion would be great!</p>