title: Split overlapping intervals into non-overlapping intervals, within values of an identifier
body: <p>I would like to take a set of intervals, possibly overlapping, within categories of an identifier and create new intervals that are either exactly overlapping (ie same start/end values) or completely non-overlapping. These new intervals should collectively span the range of the original intervals and not include any ranges not in the original intervals.</p>
  
  <p>This needs to be a relatively fast operation because I'm working with lots of data.</p>
  
  <p>Here is some example data:</p>
  
  <pre><code>library(data.table)
  set.seed(1113)
  start1 &lt;- c(1,7,9, 17, 18,1,3,20)
  end1 &lt;- c(10,12,15, 20, 23,3,5,25)
  id1 &lt;- c(1,1,1,1,1,2,2,2)
  obs &lt;- rnorm(length(id1))
  x &lt;- data.table(start1,end1,id1,obs)
  
      &gt; x
     start1 end1 id1         obs
  1:      1   10   1 -0.79701638
  2:      7   12   1 -0.09251333
  3:      9   15   1 -0.08118742
  4:     17   20   1 -2.33312797
  5:     18   23   1  0.26581138
  6:      1    3   2 -0.34314127
  7:      3    5   2 -0.17196880
  8:     20   25   2  0.11614842
  </code></pre>
  
  <p>The output should be something like this:</p>
  
  <pre><code>    id1 start1 end1 i.start1 i.end1         obs
   1:   1      1    6        1     10 -0.79701638
   2:   1      7    8        1     10 -0.79701638
   3:   1      7    8        7     12 -0.09251333
   4:   1      9   10        1     10 -0.79701638
   5:   1      9   10        7     12 -0.09251333
   6:   1      9   10        9     15 -0.08118742
   7:   1     11   12        7     12 -0.09251333
   8:   1     11   12        9     15 -0.08118742
   9:   1     13   15        9     15 -0.08118742
  10:   1     17   17       17     20 -2.33312797
  11:   1     18   20       17     20 -2.33312797
  12:   1     18   20       18     23  0.26581138
  13:   1     21   23       18     23  0.26581138
  14:   2      1    2        1      3 -0.34314127
  15:   2      3    3        1      3 -0.34314127
  16:   2      3    3        3      5 -0.17196880
  17:   2      4    5        3      5 -0.17196880
  18:   2     20   25       20     25  0.11614842
  </code></pre>
  
  <p>I found this algorithm that corresponds to what I want:
  <a href="https://softwareengineering.stackexchange.com/questions/363091/split-overlapping-ranges-into-all-unique-ranges?newreg=93383e379afe4dd3a595480528ee1541">https://softwareengineering.stackexchange.com/questions/363091/split-overlapping-ranges-into-all-unique-ranges?newreg=93383e379afe4dd3a595480528ee1541</a></p>
  
  <p>I tried programming it directly but it was quite slow.</p>