title: Data structure for non-overlapping ranges within a single dimension
body: <p>I need a data structure that can store non-overlapping ranges within a single dimension. The entire range of the dimension need not be completely covered.</p>
  
  <p>An example would be a conference room scheduler. The dimension is time. No two schedules may overlap. The conference room isn't always scheduled. In other words, for a given time there can be at most one schedule.</p>
  
  <p>A quick solution is for a range to store the start and end times.</p>
  
  <pre><code>Range {
      Date start
      Date end
  }
  </code></pre>
  
  <p>This is non-normalized and requires the container to enforce no overlapping. For two adjacent ranges, the previous' end will be redundant with the next's start.</p>
  
  <p>Another scheme might involve storing one boundary value with each range. But for a contiguous sequence of ranges, there will always be one more boundary values than ranges. To get around this the sequence could be represented as alternating boundary values and ranges:</p>
  
  <p>B = boundary value, r = range</p>
  
  <blockquote>
    <p>B-r-B-r-B</p>
  </blockquote>
  
  <p>The data structure might look like:</p>
  
  <pre><code>Boundary {
      Date value
      Range prev
      Range next
  }
  
  Range {
      Boundary start
      Boundary end
  }
  </code></pre>
  
  <p>In essence it's a doubly linked list with alternating types.</p>
  
  <p>Ultimately, whatever data structure I use will be represented in both memory (application code) and a relational database.</p>
  
  <p>I'm curious what academic or industry tried solutions exists.</p>