{"id":100989,"date":"2024-01-02T16:37:08","date_gmt":"2024-01-02T16:37:08","guid":{"rendered":"https:\/\/www.red-gate.com\/simple-talk\/?p=100989"},"modified":"2026-04-30T09:26:02","modified_gmt":"2026-04-30T09:26:02","slug":"two-dimensional-interval-packing-challenge","status":"publish","type":"post","link":"https:\/\/www.red-gate.com\/simple-talk\/databases\/sql-server\/t-sql-programming-sql-server\/two-dimensional-interval-packing-challenge\/","title":{"rendered":"Two-Dimensional Interval Packing in SQL Server: Itzik Ben-Gan’s Unpack\/Pack Solution"},"content":{"rendered":"

This article extends the classic one-dimensional interval-packing problem to two dimensions, using a student-scheduling scenario where each record spans both a date range and a class-period range. The challenge was posed to Itzik Ben-Gan by Paul Wilcox and the article presents both the task and Ben-Gan’s solution in full T-SQL. <\/strong><\/p>\n

The solution applies the Unpack\/Pack technique – converting intervals into their constituent unit points, grouping those points with a gaps-and-islands approach, and converting the groups back into packed intervals – iteratively across both dimensions. <\/strong><\/p>\n

Expected readers: advanced T-SQL developers, those familiar with Ben-Gan’s earlier packing-intervals work, and anyone who has hit this problem in scheduling, resource allocation, or calendar-overlap workloads.<\/strong><\/p>\n

What is the packing intervals task in SQL Server?\u00a0<\/h2>\n

Packing intervals is a classic SQL task that involves packing groups of intersecting intervals to their respective continuous intervals. In mathematics, an interval is the subset of all values of a given type, e.g., integer numbers, between some low value and some high value. In databases, intervals can manifest as date and time intervals representing things like sessions, prescription periods, hospitalization periods, schedules, or numeric intervals representing things like ranges of mile posts on a road, temperature ranges, and so on.<\/p>\n

An example for an interval packing task is packing intervals representing sessions for billing purposes<\/a>. If you conduct a web search of the term packing intervals SQL<\/em><\/a>, you\u2019ll find scores of articles on the subject, including my own.<\/p>\n

I\u2019ve dealt with many interval packing tasks in the past and used different techniques to handle those. But they all had something in common that kept the complexity level at bay\u2014they were all what you can think of as one-dimensional interval packing tasks. That is, each input represented one interval. One-dimensional intervals can be depicted spatially as segments on a line, and the packing task can be illustrated as identifying the delimiters of the groups of intersecting segments.<\/p>\n

During a T-SQL class, while discussing packing challenges, Paul Wilcox<\/a> from Johns Hopkins inquired whether I dealt with two-dimensional packing tasks, and if I had any references to resources for addressing those. He pointed to a forum post<\/a> he submitted a few years earlier with a problem that came about due to a scheduling issue he came across when working at a previous school district. I remember Paul trying to use hand gestures representing two dimensional polygons to illustrate the idea. Up to that point it didn\u2019t even occur to me that two-dimensional packing problems even existed, so obviously I had nothing to give him at the time. I promised to look at it after class, though, and address it next morning.<\/p>\n

I sometimes refer to solutions or techniques as being elegant. What was interesting about this problem is that the challenge itself was very elegant and compelling. Moreover, I could tell that Paul was very experienced and bright, so if after years since he first stumbled into this task, he was still looking for additional solutions, it had to be a very interesting one.<\/p>\n

In this article I present Paul\u2019s two-dimensional packing challenge and my solution. Some of the illustrations I use are like Paul\u2019s own depictions of the logical steps that are involved in the solution.<\/p>\n

As a practice tool, I recommend that you attempt to solve the challenge yourself before looking at Paul\u2019s and my solutions. I recommend reading Paul\u2019s post<\/a> to understand the task, but will also provide full details of the challenge here.<\/p>\n

Note: the code for this article can be downloaded here<\/a>.<\/p>\n

The Two-Dimensional Interval Packing Challenge<\/h2>\n

The task at hand involves student class schedules stored in a table called Schedule, which you create and populate using the following code:<\/p>\n

SET NOCOUNT ON;\nUSE tempdb;\nDROP TABLE IF EXISTS dbo.Schedule;\nCREATE TABLE dbo.Schedule\n(\n  id         INT     NOT NULL \n     CONSTRAINT PK_Schedule PRIMARY KEY,\n  student    CHAR(3) NOT NULL,\n  fromdate   INT     NOT NULL,\n  todate     INT     NOT NULL,\n  fromperiod INT     NOT NULL,\n  toperiod   INT     NOT NULL\n);\nINSERT INTO dbo.Schedule(id, student, fromdate, todate, \nfromperiod, toperiod) VALUES\n    (1, 'Amy',  1,  7,  7,  9),\n    (2, 'Amy',  3,  9,  5,  8), \n    (3, 'Amy', 10, 12,  1,  3), \n    (4, 'Ted',  1,  5, 11, 14),\n    (5, 'Ted',  7, 11, 13, 16);<\/pre>\n
Each row has the student in question, a begin date (fromdate<\/code>) and end date (todate<\/code>), and a period start time (fromperiod<\/code>) and period end time (toperiod<\/code>). Note that the sample data uses integers instead of date and time values for simplicity.<\/p>\n
To help understand the current data, it can be convenient to depict it graphically. This can be achieved with the following spatial query, forming a rectangle from each row:<\/p>\n
SELECT student,\n  GEOMETRY::STGeomFromText('GEOMETRYCOLLECTION('\n  + STRING_AGG(CONCAT('POLYGON((',fromdate,' ',fromperiod, ',', \n                                fromdate,' ',toperiod + 1, ',', \n                                todate + 1,' ',toperiod + 1,',', \n                                todate + 1,' ',fromperiod,',', \n                                fromdate,' ',fromperiod ,    \n                  '))'), ',') \n + ')', 0) AS shape\nFROM dbo.Schedule\nGROUP BY student;<\/pre>\n
Figure 1 has the graphical output of this query as can be seen in the SSMS Spatial results tab.<\/p>\n
<\/p>\n
Figure 1: Unnormalized Schedule Depicted Graphically<\/strong><\/p>\n
The X axis represents the date ranges, and the Y axis represents the period ranges.<\/p>\n
Notice that a student may have overlapping schedules, as is the case with Amy\u2019s schedules 1 and 2. You can think of the current data as representing an unnormalized form of the schedule.<\/p>\n
Sometimes you need to query the data to identify a schedule that contains a certain date and period. For example, the following query looks for Amy’s schedule that contains date 4 and period 8:<\/p>\n
SELECT id, student, fromdate, todate, fromperiod, toperiod\nFROM dbo.Schedule\nWHERE student = 'Amy'\n  AND 4 BETWEEN fromdate AND todate\n  AND 8 BETWEEN fromperiod AND toperiod;<\/pre>\n
This query generates the following output, showing multiple matches:<\/p>\n
id          student fromdate    todate      fromperiod  toperiod\n----------- ------- ----------- ----------- ----------- --------\n1           Amy     1           7           7           9\n2           Amy     3           9           5           8<\/pre>\n
Multiple matches for a single (date, period) point are only possible due to the unnormalized nature of the schedule. The challenge is to create a normalized state of the schedule, with distinct, nonoverlapping date range and period range combinations. Assuming such a normalized state is stored in a table, you then have a guarantee for no more than one matching row per input (date, period) point.<\/p>\n
The tricky part is that there may be multiple arrangements that can achieve this goal. For the sake of this challenge, you just need to pick one that produces a deterministic result. For example, form a result row for each consecutive range of dates with the same period range. Figure 2 has a graphical depiction of the desired normalized schedule.<\/p>\n
<\/p>\n
Figure 2: Desired Normalized Schedule<\/strong><\/p>\n
Informally, you\u2019re forming the smallest number of rectangles possible using only vertical cuts. Obviously, you could go for a strategy that uses horizontal cuts. Or even something more sophisticated that uses a combination of vertical and horizontal cuts. Anyway, assuming the vertical-cuts approach, following is the desired output of your solution:<\/p>\n
student fromdate    todate      fromperiod  toperiod\n------- ----------- ----------- ----------- -----------\nAmy     1           2           7           9\nAmy     3           7           5           9\nAmy     8           9           5           8\nAmy     10          12          1           3\nTed     1           5           11          14\nTed     7           11          13          16<\/pre>\n
Told you it\u2019s a formidable challenge. Now, to work!<\/p>\n
Unpack\/Pack Solution for One Dimensional Packing<\/h2>\n
My approach to solving the two-dimensional packing problem is to rely on a classic technique for handling one-dimensional packing, which you can think of as the Unpack\/Pack technique, in multiple steps of the solution. So first, let me describe the Unpack\/Pack technique for one-dimensional packing.<\/p>\n
Suppose that in our Schedule table you only had period ranges and needed to normalize them. This is of course a completely contrived example, but I\u2019m using it for convenience since we already have sample data available to work with. Here\u2019s a query showing just the periods:<\/p>\n
SELECT id, student, fromperiod, toperiod\nFROM dbo.Schedule\nORDER BY student, fromperiod, toperiod;<\/pre>\n
This query generates the following output:<\/p>\n
id          student fromperiod  toperiod\n----------- ------- ----------- -----------\n3           Amy     1           3\n2           Amy     5           8\n1           Amy     7           9\n4           Ted     11          14\n5           Ted     13          16<\/pre>\n
Suppose that the task was to pack intersecting periods per student. Here\u2019s the desired output of the solution with the packed periods:<\/p>\n
student fromperiod  toperiod\n------- ----------- -----------\nAmy     1           3\nAmy     5           9\nTed     11          16<\/pre>\n
As mentioned earlier, there are many solutions out there for packing intervals. The Unpack\/Pack solution involves the following steps:<\/p>\n
    \n
  1. Unpack each interval to the individual values that constitute the set.<\/li>\n
  2. Compute a group identifier using a classic islands technique<\/a>.<\/li>\n
  3. Group the data by the group identifier to form the packed intervals.<\/li>\n<\/ol>\n
    Let\u2019s start with Step 1. You\u2019re supposed to unpack each interval to the individual values that constitute the interval set. Recall that an interval is the set of all values between the low and high values representing the interval delimiters. For example, given that our sample data uses an integer type for the period delimiters, Amy\u2019s interval with fromperiod<\/code> 5<\/code> and toperiod<\/code> 8<\/code> should be unpacked to the set {5, 6, 7, 8}<\/code>.<\/p>\n
    If you\u2019re using Azure SQL or SQL Server 2022 or above, you can achieve this with the GENERATE_SERIES<\/code> function, like so:<\/p>\n
    SELECT S.id, S.student, P.value AS p\nFROM dbo.Schedule AS S\n  CROSS APPLY GENERATE_SERIES(S.fromperiod, S.toperiod) AS P\nORDER BY S.student, p, S.id;<\/pre>\n
    This query generates the following output:<\/p>\n
    id          student p\n----------- ------- -----------\n3           Amy     1\n3           Amy     2\n3           Amy     3\n2           Amy     5\n2           Amy     6\n1           Amy     7\n2           Amy     7\n1           Amy     8\n2           Amy     8\n1           Amy     9\n4           Ted     11\n4           Ted     12\n4           Ted     13\n5           Ted     13\n4           Ted     14\n5           Ted     14\n5           Ted     15\n5           Ted     16<\/pre>\n
    If you don\u2019t have access to the GENERATE_SERIES<\/code> function, you can either create your own<\/a>, or use a numbers table.<\/p>\n
    Step 2 involves computing a unique group identifier per packed interval. Observe that each packed interval contains a consecutive range of unpacked p values, possibly with duplicates. As an example, see Amy\u2019s range between 5<\/code> and 9<\/code>: {5, 6, 7, 7, 8, 8, 9}<\/code>. The group identifier can be computed as the p value, minus the dense rank value (because there may be duplicates) based on p value ordering, within the student partition. Here\u2019s the query that achieves this, showing also the dense rank values separately for clarity:<\/p>\n
    SELECT S.id, S.student, P.value AS p,\n  DENSE_RANK() OVER(PARTITION BY S.student ORDER BY P.value) \n                                                     AS drk,\n  P.value - DENSE_RANK() OVER(PARTITION BY S.student \n                              ORDER BY P.value) AS grp_p\nFROM dbo.Schedule AS S\n  CROSS APPLY GENERATE_SERIES(S.fromperiod, S.toperiod) AS P\nORDER BY S.student, p, S.id;<\/pre>\n
    This query generates the following output:<\/p>\n
    id          student p      drk       grp_p\n----------- ------- ------ --------- --------\n3           Amy     1      1         0\n3           Amy     2      2         0\n3           Amy     3      3         0\n2           Amy     5      4         1\n2           Amy     6      5         1\n1           Amy     7      6         1\n2           Amy     7      6         1\n1           Amy     8      7         1\n2           Amy     8      7         1\n1           Amy     9      8         1\n4           Ted     11     1         10\n4           Ted     12     2         10\n4           Ted     13     3         10\n5           Ted     13     3         10\n4           Ted     14     4         10\n5           Ted     14     4         10\n5           Ted     15     5         10\n5           Ted     16     6         10<\/pre>\n
    You get a group identifier (grp_p<\/code>) that is the same per packed interval group and unique per group.<\/p>\n
    Step 3 then groups the unpacked data by the student and the group identifier, and computes the packed interval delimiters with the MIN(p)<\/code> an MAX(p)<\/code> aggregates, like so:<\/p>\n
    WITH C AS\n(\n  SELECT S.id, S.student, P.value AS p,\n    DENSE_RANK() OVER(PARTITION BY S.student ORDER BY P.value) \n                                                       AS drk,\n    P.value - DENSE_RANK() OVER(PARTITION BY S.student \n                                ORDER BY P.value) AS grp_p\n  FROM dbo.Schedule AS S\n    CROSS APPLY GENERATE_SERIES(S.fromperiod, S.toperiod) AS P\n)\nSELECT student, MIN(p) AS fromperiod, MAX(p) AS toperiod\nFROM C\nGROUP BY student, grp_p\nORDER BY student, fromperiod;<\/pre>\n
    This query generates the following desired output:<\/p>\n
    student fromperiod  toperiod\n------- ----------- -----------\nAmy     1           3\nAmy     5           9\nTed     11          16<\/pre>\n
    This technique is obviously not very optimal when the sets representing the intervals can contain large numbers of members. But it works quite well for small sets and is essential for handling the two-dimensional packing challenge.<\/p>\n
    Solution for Two-Dimensional Packing<\/h3>\n
    Armed with the Unpack\/Pack technique, you are ready to tackle the two-dimensional packing task. The trick is to realize that you can use it multiple times in the solution\u2014once per dimension.<\/p>\n
    In Step 1, you unpack the two-dimensional date range, period range values to the individual date (d)<\/code>, period (p)<\/code> values. It\u2019s probably easiest to think of this step in graphical terms, as pixelating (thanks Paul for the terminology!) the rectangles representing each student class schedule from Figure 1 shown earlier. Here\u2019s the code to achieve this step:<\/p>\n
    SELECT S.id, S.student, D.value AS d, P.value AS p\nFROM dbo.Schedule AS S\n  CROSS APPLY GENERATE_SERIES(S.fromdate, S.todate) AS D\n  CROSS APPLY GENERATE_SERIES(S.fromperiod, S.toperiod) AS P\nORDER BY S.student, d, p, S.id;<\/pre>\n
    This query generates the following output:<\/p>\n
    id          student d           p\n----------- ------- ----------- -----------\n1           Amy     1           7\n1           Amy     1           8\n1           Amy     1           9\n1           Amy     2           7\n1           Amy     2           8\n1           Amy     2           9\n2           Amy     3           5\n2           Amy     3           6\n1           Amy     3           7\n2           Amy     3           7\n1           Amy     3           8\n2           Amy     3           8\n1           Amy     3           9\n2           Amy     4           5\n2           Amy     4           6\n1           Amy     4           7\n2           Amy     4           7\n1           Amy     4           8\n2           Amy     4           8\n1           Amy     4           9\n2           Amy     5           5\n2           Amy     5           6\n1           Amy     5           7\n2           Amy     5           7\n1           Amy     5           8\n2           Amy     5           8\n1           Amy     5           9\n2           Amy     6           5\n2           Amy     6           6\n1           Amy     6           7\n2           Amy     6           7\n1           Amy     6           8\n2           Amy     6           8\n1           Amy     6           9\n2           Amy     7           5\n2           Amy     7           6\n1           Amy     7           7\n2           Amy     7           7\n1           Amy     7           8\n2           Amy     7           8\n1           Amy     7           9\n2           Amy     8           5\n2           Amy     8           6\n2           Amy     8           7\n2           Amy     8           8\n2           Amy     9           5\n2           Amy     9           6\n2           Amy     9           7\n2           Amy     9           8\n3           Amy     10          1\n3           Amy     10          2\n3           Amy     10          3\n3           Amy     11          1\n3           Amy     11          2\n3           Amy     11          3\n3           Amy     12          1\n3           Amy     12          2\n3           Amy     12          3\n...<\/pre>\n
    You can use the following helper query to depict Step 1’s result graphically:<\/p>\n
    WITH Pixels AS\n(\n  SELECT S.id, S.student, D.value AS d, P.value AS p\n  FROM dbo.Schedule AS S\n    CROSS APPLY GENERATE_SERIES(S.fromdate, S.todate) AS D\n    CROSS APPLY GENERATE_SERIES(S.fromperiod, S.toperiod) AS P\n)\nSELECT student,\n  GEOMETRY::STGeomFromText('GEOMETRYCOLLECTION('\n    + STRING_AGG(CONCAT('POLYGON((', d    , ' ', p    , ',', \n                                     d    , ' ', p + 1, ',', \n                                     d + 1, ' ', p + 1, ',', \n                                     d + 1, ' ', p    , ',', \n                                     d    , ' ', p    , '))'), ',') \n    + ')', 0) AS shape\nFROM Pixels\nGROUP BY student;<\/pre>\n
    Figure 3 has the graphical result from the Spatial results tab in SSMS.<\/p>\n
    <\/p>\n
    Figure 3: Pixelated Schedule<\/strong><\/p>\n
    Now you need to decide on the normalization strategy that you want to use. Assuming you decide to use what I referred to earlier as the vertical cuts approach, you can proceed to Step 2. To apply vertical cuts, you pack period ranges per student and date. This is achieved by assigning the group identifier grp_p to each distinct range of consecutive p values per student and d group. Here\u2019s the code that achieves this:<\/p>\n
    WITH PixelsAndPeriodGroupIDs AS\n(\n  SELECT S.id, S.student, D.value AS d, P.value AS p,\n    P.value - DENSE_RANK() OVER(PARTITION BY S.student, D.value \n                                ORDER BY P.value) AS grp_p\n  FROM dbo.Schedule AS S\n    CROSS APPLY GENERATE_SERIES(S.fromdate, S.todate) AS D\n    CROSS APPLY GENERATE_SERIES(S.fromperiod, S.toperiod) AS P\n)\nSELECT student, d, MIN(p) AS fromperiod, MAX(p) AS toperiod\nFROM PixelsAndPeriodGroupIDs\nGROUP BY student, d, grp_p\nORDER BY student, d, grp_p;<\/pre>\n
    Here\u2019s the output of the inner query defining the CTE PixelsAndPeriodGroupIDs<\/code>, showing the computed grp_p<\/code> value per pixel, if you will:<\/p>\n
    id          student d           p           grp_p\n----------- ------- ----------- ----------- --------------------\n1           Amy     1           7           6\n1           Amy     1           8           6\n1           Amy     1           9           6\n1           Amy     2           7           6\n1           Amy     2           8           6\n1           Amy     2           9           6\n2           Amy     3           5           4\n2           Amy     3           6           4\n2           Amy     3           7           4\n1           Amy     3           7           4\n1           Amy     3           8           4\n2           Amy     3           8           4\n1           Amy     3           9           4\n2           Amy     4           5           4\n2           Amy     4           6           4\n2           Amy     4           7           4\n1           Amy     4           7           4\n1           Amy     4           8           4\n2           Amy     4           8           4\n1           Amy     4           9           4\n2           Amy     5           5           4\n2           Amy     5           6           4\n2           Amy     5           7           4\n1           Amy     5           7           4\n1           Amy     5           8           4\n2           Amy     5           8           4\n1           Amy     5           9           4\n2           Amy     6           5           4\n2           Amy     6           6           4\n2           Amy     6           7           4\n1           Amy     6           7           4\n1           Amy     6           8           4\n2           Amy     6           8           4\n1           Amy     6           9           4\n2           Amy     7           5           4\n2           Amy     7           6           4\n2           Amy     7           7           4\n1           Amy     7           7           4\n1           Amy     7           8           4\n2           Amy     7           8           4\n1           Amy     7           9           4\n2           Amy     8           5           4\n2           Amy     8           6           4\n2           Amy     8           7           4\n2           Amy     8           8           4\n2           Amy     9           5           4\n2           Amy     9           6           4\n2           Amy     9           7           4\n2           Amy     9           8           4\n3           Amy     10          1           0\n3           Amy     10          2           0\n3           Amy     10          3           0\n3           Amy     11          1           0\n3           Amy     11          2           0\n3           Amy     11          3           0\n3           Amy     12          1           0\n3           Amy     12          2           0\n3           Amy     12          3           0\n\u2026<\/pre>\n
    And here\u2019s the output of outer query, showing the packed period ranges after grouping:<\/p>\n
    student d           fromperiod  toperiod\n------- ----------- ----------- -----------\nAmy     1           7           9\nAmy     2           7           9\nAmy     3           5           9\nAmy     4           5           9\nAmy     5           5           9\nAmy     6           5           9\nAmy     7           5           9\nAmy     8           5           8\nAmy     9           5           8\nAmy     10          1           3\nAmy     11          1           3\nAmy     12          1           3\nTed     1           11          14\nTed     2           11          14\nTed     3           11          14\nTed     4           11          14\nTed     5           11          14\nTed     7           13          16\nTed     8           13          16\nTed     9           13          16\nTed     10          13          16\nTed     11          13          16<\/pre>\n
    What\u2019s important to note here is that you created packed period ranges per student and date. This is convenient to depict graphically using the following spatial query:<\/p>\n
    WITH PixelsAndPeriodGroupIDs AS\n(\n  SELECT S.id, S.student, D.value AS d, P.value AS p,\n    P.value - DENSE_RANK() OVER(PARTITION BY S.student, D.value \n                                ORDER BY P.value) AS grp_p\n  FROM dbo.Schedule AS S\n    CROSS APPLY GENERATE_SERIES(S.fromdate, S.todate) AS D\n    CROSS APPLY GENERATE_SERIES(S.fromperiod, S.toperiod) AS P\n),\nDailyPeriodRanges AS\n(\n  SELECT student, d, MIN(p) AS fromperiod, MAX(p) AS toperiod\n  FROM PixelsAndPeriodGroupIDs\n  GROUP BY student, d, grp_p\n)\nSELECT student,\n  GEOMETRY::STGeomFromText('GEOMETRYCOLLECTION('\n    + STRING_AGG(CONCAT('POLYGON((',d,' ',fromperiod  , ',', \n                                 d,' ',toperiod + 1,',', \n                                 d + 1,' ',toperiod + 1, ',', \n                                 d + 1,' ',fromperiod ,',',\n                                 d,' ',fromperiod,'))'),',') \n    + ')', 0) AS shape\nFROM DailyPeriodRanges\nGROUP BY student;<\/pre>\n
    The output from the Spatial results tab in SSMS shown in Figure 4.<\/p>\n
    <\/p>\n
    Figure 4: Daily Period Ranges<\/strong><\/p>\n
    What you achieved here is sort of daily binning (again, thanks Paul for the terminology) of the packed period ranges. What\u2019s left then in Step 3, is to pack consecutive date ranges per student and period range. Here\u2019s the code to achieve this:<\/p>\n
    WITH PixelsAndPeriodGroupIDs AS\n(\n  SELECT S.id, S.student, D.value AS d, P.value AS p,\n    P.value - DENSE_RANK() OVER(PARTITION BY S.student, D.value \n                                ORDER BY P.value) AS grp_p\n  FROM dbo.Schedule AS S\n    CROSS APPLY GENERATE_SERIES(S.fromdate, S.todate) AS D\n    CROSS APPLY GENERATE_SERIES(S.fromperiod, S.toperiod) AS P\n),\nPeriodRangesAndDateGroupIDs AS\n(\n  SELECT student, d, MIN(p) AS fromperiod, MAX(p) AS toperiod,\n    D - DENSE_RANK() OVER(PARTITION BY student, MIN(p), MAX(p) \n                          ORDER BY d) as grp_d\n  FROM PixelsAndPeriodGroupIDs\n  GROUP BY student, d, grp_p\n)\nSELECT student, MIN(d) AS fromdate, MAX(d) AS todate, \n       fromperiod, toperiod\nFROM PeriodRangesAndDateGroupIDs\nGROUP BY student, fromperiod, toperiod, grp_d\nORDER BY student, fromdate, fromperiod;<\/pre>\n
    The main trick here is that in the second CTE (PeriodRangesAndDateGroupIDs<\/code>), where you apply the classic islands technique a second time, when computing the dense rank value, you partition it by the student and the period range (student<\/code>, MIN(p)<\/code>, MAX(p)<\/code>), and order it by d.<\/p>\n
    Here\u2019s the output of the second CTE\u2019s inner query:<\/p>\n
    student d           fromperiod  toperiod    grp_d\n------- ----------- ----------- ----------- ----------\nAmy     10          1           3           9\nAmy     11          1           3           9\nAmy     12          1           3           9\nAmy     8           5           8           7\nAmy     9           5           8           7\nAmy     3           5           9           2\nAmy     4           5           9           2\nAmy     5           5           9           2\nAmy     6           5           9           2\nAmy     7           5           9           2\nAmy     1           7           9           0\nAmy     2           7           9           0\nTed     1           11          14          0\nTed     2           11          14          0\nTed     3           11          14          0\nTed     4           11          14          0\nTed     5           11          14          0\nTed     7           13          16          6\nTed     8           13          16          6\nTed     9           13          16          6\nTed     10          13          16          6\nTed     11          13          16          6<\/pre>\n
    And here\u2019s the output of the outer query, showing the final desired result with the normalized schedule:<\/p>\n
    student fromdate    todate      fromperiod  toperiod\n------- ----------- ----------- ----------- -----------\nAmy     1           2           7           9\nAmy     3           7           5           9\nAmy     8           9           5           8\nAmy     10          12          1           3\nTed     1           5           11          14\nTed     7           11          13          16<\/pre>\n
    If you wish to illustrate the result graphically, you can use the following helper spatial query:<\/p>\n
    WITH PixelsAndPeriodGroupIDs AS\n(\n  SELECT S.id, S.student, D.value AS d, P.value AS p,\n    P.value - DENSE_RANK() OVER(PARTITION BY S.student, D.value\n                                ORDER BY P.value) AS grp_p\n  FROM dbo.Schedule AS S\n    CROSS APPLY GENERATE_SERIES(S.fromdate, S.todate) AS D\n    CROSS APPLY GENERATE_SERIES(S.fromperiod, S.toperiod) AS P\n),\nPeriodRangesAndDateGroupIDs AS\n(\n  SELECT student, d, MIN(p) AS fromperiod, MAX(p) AS toperiod,\n    d - DENSE_RANK() OVER(PARTITION BY student, MIN(p), MAX(p) \n                          ORDER BY d) as grp_d\n  FROM PixelsAndPeriodGroupIDs\n  GROUP BY student, d, grp_p\n),\nNormalizedSchedule AS\n(\n  SELECT student, MIN(d) AS fromdate, MAX(d) AS todate, \n        fromperiod, toperiod\n  FROM PeriodRangesAndDateGroupIDs\n  GROUP BY student, fromperiod, toperiod, grp_d\n)\nSELECT student,\n  GEOMETRY::STGeomFromText('GEOMETRYCOLLECTION('\n   + STRING_AGG(CONCAT('POLYGON((',fromdate,' ',fromperiod,',',\n                                  fromdate,' ',toperiod+1,',',\n                                  todate + 1,' ',toperiod+1,',',\n                                  todate + 1,' ',fromperiod,',', \n                                  fromdate  , ' ', fromperiod  ,   \n                               '))'), \n     ',') \n+ ')', 0) AS shape\nFROM NormalizedSchedule\nGROUP BY student;<\/pre>\n
    The output in the Spatial results tab in SSMS is the same as what I\u2019ve shown earlier in Figure 2 as the graphical depiction of the desired result.<\/p>\n
    Conclusion<\/h2>\n
    Thanks again to Paul Wilcox for introducing the two-dimensional packing challenge. It\u2019s a beautiful puzzler and I enjoyed very much working on it. I hope that\u2019s the case for you too.<\/p>\n
    You saw how important it is to develop a toolbox of fundamental techniques, such as the classic islands technique, and based on it, the Unpack\/Pack technique. Those were essential for solving this more complex challenge. You also saw how useful it can be to think of some tasks in graphical terms, and even utilize T-SQL spatial tools for this purpose.<\/p>\n
    Happy querying!<\/p>\n
    \u00a0<\/p>\n\n\n
    \n    
    FAQs<\/h2>\n\n                        
    1. What is the interval packing problem in SQL?<\/h3>\n            
    \n                
    Interval packing is the task of consolidating groups of overlapping or adjacent intervals into their continuous equivalents. Given a set of intervals (e.g., sessions 9-11, 10-12, 14-16), packing produces the minimum set of non-overlapping intervals that cover the same points (9-12, 14-16). It’s common in scheduling, resource allocation, billing consolidation, and time-series analysis. The one-dimensional version has established T-SQL solutions; the two-dimensional extension – where intervals span two axes such as date-and-period – is less commonly documented.<\/p>\n            <\/div>\n                    
    2. What is the Unpack\/Pack technique in SQL Server?<\/h3>\n            
    \n                
    Unpack\/Pack is a set-based interval-packing technique where you: (1) Unpack – convert each interval into a row per discrete unit point it covers (so interval 5-8 becomes rows for 5, 6, 7, 8); (2) apply a gaps-and-islands analysis to group consecutive points into islands; (3) Pack – convert each island back into an interval by taking its MIN and MAX. The technique is purely set-based (no cursors) and scales well on modern SQL Server. The article demonstrates applying it iteratively across two dimensions by repeating the process along the second axis after packing the first.<\/p>\n            <\/div>\n                    
    3. How do you pack intervals across two dimensions in SQL Server?<\/h3>\n            
    \n                
    Apply the Unpack\/Pack technique to one dimension first, then apply it again to the result in the second dimension. For student scheduling with date and period axes: first unpack each schedule record into per-day-per-period rows, pack those into contiguous date runs per period per student, then unpack those by period and pack into contiguous period runs. The result is the minimum set of two-dimensional rectangles that cover the original input. The key insight is that two-dimensional packing reduces to two sequential one-dimensional packings if the ordering is chosen correctly.<\/p>\n            <\/div>\n                    
    4. Can I solve interval packing without using cursors?<\/h3>\n            
    \n                
    Yes. All efficient interval-packing solutions in SQL Server are fully set-based – no cursors needed. The Unpack\/Pack approach, LAG-based consecutive-row comparisons, and row-number difference techniques (borrowed from gaps-and-islands analysis) all operate on the input set as a whole. Cursor-based solutions exist but are much slower and should not be used in production. For large datasets (millions of rows), index the sort column used in the packing step and ensure statistics are current – the SQL Server query optimiser handles the rest.<\/p>\n            <\/div>\n            <\/section>\n","protected":false},"excerpt":{"rendered":"
    Itzik Ben-Gan’s two-dimensional interval packing challenge in SQL Server: packing overlapping student schedule intervals across date and period axes. Complete T-SQL solution using the Unpack\/Pack technique applied iteratively in both dimensions.…<\/p>\n","protected":false},"author":341753,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[53,143531,143539],"tags":[],"coauthors":[158990],"class_list":["post-100989","post","type-post","status-publish","format-standard","hentry","category-featured","category-t-sql-programming-sql-server","category-theory-and-design"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/100989","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/users\/341753"}],"replies":[{"embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/comments?post=100989"}],"version-history":[{"count":4,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/100989\/revisions"}],"predecessor-version":[{"id":110220,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/100989\/revisions\/110220"}],"wp:attachment":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/media?parent=100989"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/categories?post=100989"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/tags?post=100989"},{"taxonomy":"author","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/coauthors?post=100989"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}