title: Simultaneously Aggregating Overlapping Ranges (A Rectangle Problem)
body: <h2>My Problem</h2>
  
  <p>Consider a set of data with two intervals.  For instance, consider a student schedule of classes.  Each record has a begin and end date, and each class has a period start time and a period end time.  But this schedule is not 'normalized' in the sense that some records overlap.  So if you search for records encompassing a given date and period for a student, you might get multiple matches.  </p>
  
  <p>Here's a contrived example.  I represent the dates as integers to simplify the problem:</p>
  
  <pre><code>declare @schedule table (
      student char(3),
      fromDate int,
      toDate int,
      fromPeriod int,
      toPeriod int
  )
  
  insert @schedule values
      ('amy', 1, 7, 7, 9),
      ('amy', 3, 9, 5, 8), 
      ('amy', 10, 12, 1, 3), 
      ('ted', 1, 5, 11, 14),
      ('ted', 7, 11, 13, 16); 
  </code></pre>
  
  <p>Amy's date and period ranges either overlap or are adjacent.  If I queried for 'date 5 period 7', I would get two matches.  I need these reworked so that they represent the same 'area' but no longer overlap. </p>
  
  <p>Ted's periods overlap but his dates do not.  This means there's no real overlap, so no need to re-work anything.</p>
  
  <h2>My Research</h2>
  
  <p>I've read many posts and some articles on working overlapping intervals. Namely:</p>
  
  <ul>
  <li><a href="https://stackoverflow.com/questions/2561130/merge-overlapping-date-intervals">Merge overlapping date intervals</a> </li>
  <li><a href="https://stackoverflow.com/questions/964288/flattening-intersecting-timespans">Flattening intersecting timespans</a></li>
  <li><a href="https://stackoverflow.com/questions/35498285/condense-time-periods-with-sql">Condense Time Periods with SQL</a> </li>
  <li><a href="https://stackoverflow.com/questions/30641259/sql-server-cumulative-sum-on-overlapping-data-getting-date-that-sum-reaches">SQL Server - cumulative sum on overlapping data - getting date that sum reaches a given value</a> </li>
  <li><a href="https://stackoverflow.com/questions/21468645/flatten-merge-overlapping-time-intervals">Flatten/merge overlapping time intervals</a> </li>
  <li><a href="https://stackoverflow.com/questions/24795907/sql-server-separate-overlapping-dates">SQL Server separate overlapping dates</a> </li>
  </ul>
  
  <p>I've implemented one from Itzik from a blog entitled 'solutions-packing-date-and-time-intervals-puzzle' that has worked great for one particular project.  I don't think it's a stable link, but I've found a copy of it <a href="https://www.itprotoday.com/development-techniques-and-management/solutions-packing-date-and-time-intervals-puzzle" rel="nofollow noreferrer">here</a>.</p>
  
  <p>But I'm having difficulty extending the knowledge in those resources to my problem at hand.  It might be my limitation.  I have trouble following them.  I've studied Itzik's solution and have come to understand a lot of it, but I do recall there's one piece I just couldn't understand.  Or it might be that those solutions only work with singular ranges.</p>
  
  <h2>My Attempt</h2>
  
  <p>I resolved this question by treating the ranges as literal rectangle objects.  It works.  I've even made a version of it somewhat performant in my own application. So I'll post it as a solution in case it is of use to anyone with the same issue.</p>
  
  <p>But it is so long and involved and there are enough quirks to it (e.g. buffering lines, looping shapes, working with float values, rounding issues) that I can't help but think that there's a much better way.  Can the concepts of my listed resources be extended to dual ranges?  Or do some SRID's allow cutting rectangles with zero-length lines?  </p>
  
  <h2>Expected Results:</h2>
  
  <p>There is no one answer to this problem, because you can aggregate ranges and deconstruct them in different ways.  But to minimize the number of resulting rectangles, there are really only two acceptable answers.  Visually, with dates on the X axis and periods on the Y axis, overlapping ranges can start out like this:</p>
  
  <pre><code> +------------+
   |            |
   |    +------------+
   |    ||||||||     |  &lt;- 2 overlapping rectangles
   +----|            |
        |            |
        +------------+
  </code></pre>
  
  <p>We can rework it this way:</p>
  
  <pre><code> +---+ +-----+
   |   | |     |
   |   | |     | +---+  &lt;- 3 non-overlapping 
   |   | |     | |   |     vertically cut rectangles
   +---| |     | |   |
         |     | |   |
         +-----+ +---+
  </code></pre>
  
  <p>Or this way:</p>
  
  <pre><code> +-----------+
   +-----------+
  
   +-----------------+  &lt;- 3 non-overlapping 
   +-----------------+     horizontally cut rectangles
  
         +-----------+
         +-----------+
  </code></pre>
  
  <p>Going with vertical cuts, the results would look like this:</p>
  
  <pre><code>+-------------------------------------------+
  |student|fromDate|toDate|fromPeriod|toPeriod|
  |-------------------------------------------|
  |amy    |1       |2     |7         |9       |
  |amy    |3       |7     |5         |9       |
  |amy    |8       |9     |5         |8       |
  |amy    |10      |12    |1         |3       |
  |ted    |1       |5     |11        |14      |
  |ted    |7       |11    |13        |16      |
  +-------------------------------------------+
  </code></pre>
  
  <p>Going with horizontal cuts, the results would look like this:</p>
  
  <pre><code>+-------------------------------------------+
  |student|fromDate|toDate|fromPeriod|toPeriod|
  |-------------------------------------------|
  |amy    |1       |7     |9         |9       |
  |amy    |1       |9     |7         |8       |
  |amy    |3       |9     |5         |6       |
  |amy    |10      |12    |1         |3       |
  |ted    |1       |5     |11        |14      |
  |ted    |7       |11    |13        |16      |
  +-------------------------------------------+
  </code></pre>
  
  <p>Either is acceptable.  Though, to keep it deterministic and tractable, you would want to choose one strategy and stick with it.</p>