Celko’s SQL Stumper: The Class Scheduling Problem

What can we use in SQL instead of E. F. Codd's T theta operators for best-fit? Joe Celko returns with another puzzle that isn't new, in fact it already features "Swedish", "Croatian" and "Colombian" solutions in chapter 17 of Joe's 'SQL for Smarties' book. These were all written before CTEs or the new WINDOW functions. Is there now a better solution? Was there one even then? We leave it to the readers to provide the answer!

In the book “The Relational Model, Version Two” (1990, ISBN13: 978-0201141924), Dr. E. F. Codd introduced a set of new theta operators, called T-operators, which were based on the idea of a best-fit or approximate equality. The name never caught on and nobody invented special syntax for them.

One problem is that they were defined by a procedural algorithm and not a set-oriented definition. It is easier to understand with an example modified from Dr. Codd.

The problem is to assign the classes to the available classrooms. We want (class_size < room_size) to be true after the assignments are made. This will allow us a few empty seats in each room for late students. We can do this in one of two ways. The first way is to sort the tables in ascending order by classroom size and the number of students in a class. We start with the following simplified tables:

These tables have the following rows in them:

The goal of the T-JOIN problem is to assign a class which is smaller than the classroom given it (class_size < room_size). Dr. Codd gives two approaches to the problem.

1) Ascending Order Algorithm

Sort both tables in ascending order. Reading from the top of the Rooms table, match each class with the first room that will fit.

This gives us …

2) Descending Order Algorithm

Sort both tables in descending order. Reading from the top of the Classes table, match each class with the first room that will fit.

and …

Notice that the answers are different! Dr. Codd has never given a definition in relational algebra of the T-Join, so I proposed that we need one. Informally, for each class, we want the smallest room that will hold it, while maintaining
the T-JOIN condition. Or for each room, we want the largest class that will almost fill it, while maintaining the T-JOIN condition. These can be two different things, because these are not “best fit” solutions “first fit” approach.

Other theta conditions can be used in place of the “less than” shown here. If “less than or equal” is used, all the classes are assigned to a room in this case, but not in all cases. Nor is the solution always unique. Here is a (class_size <= room_size) answer for this data. Room ‘r5’ is too small to match any class.

In the third edition of SQL FOR SMARTIES, I gave “Swedish”, “Croatian” and “Colombian” solutions, named for the countries of the submitters. They were all written without CTEs or the new WINDOW functions (that is the technical name for the OVER() clause on aggregate functions). Obviously, if two rooms or two classes are the same size, they can be swapped with each other. Let’s make life easier by adding a UNIQUE constraint to room_size and class_size.

The problem is write an SQL statement that gives a T-Join.

WARNING: some of you already know this, but finding an optimal solution is an NP-complete problem. The bigger the data set gets, the effort it takes to solve the problem increase beyond any reasonable limit. You can Google for “Knapsack Problem” or  “Bin Packing Problem” if you want the details.

The best answer to each stumper will be given a prize of a $100 Amazon voucher. The stumper will be run simultaneously on SQL Server Central and Simple-Talk. To see all the comments so far, you will need to visit both sites.

 We will take entries for a week after the first Monday of publication, posted as comments to the articles.

Two weeks after the challenge is sent out, the judge’s decision and comments will be sent out in the newsletter, and published on the site. Joe Celko and Phil Factor will judge the answers to this puzzle. Your answer should :Your answer should :

  1. Solve the problem — Duh!
  2. Avoid proprietary features in SQL Server that will not port or be good across all releases, present and future.
  3. Use Standard features in SQL Server that will be good across all releases, present and future. Extra points for porting code.
  4. Be clever but not obscure.
  5. Explain how you got your answer.

Judging:
The challenge presented by ‘Celko’s SQL Stumper: The Class Scheduling Problem’  was to assign classes to the classrooms that were available. This meant that, for each assignment the class size had to be less than the room size after the assignments are made, so as to allow a few empty seats in each room for late students. During the competition, Joe decided to rule out problems such as duplicate class sizes and identical rooms, in order to avoid ‘combinatorial explosions’.

Joe had already provided some solutions to this problem in his ‘SQL for Smarties’ book but challenged contestants to come up with something better. However, if he was expecting mainly to see subtle variations on his own ideas, then he got a pleasant surprise; most of the contestants aimed for something new and different. Refreshingly, the competition turned into a real group effort.  The majority of the entries are to be found on the SQLServerCentral site, since their forum software makes it rather easier for the contestants. In many cases, interesting and imaginative solutions were submitted, and then subsequently refined and re-submitted, based on help and advice from fellow contestants. It made choosing a winner a very difficult task.

First of all, came Peso, who set a very high standard, as always, with his first and second Descending order algorithm. For a short while there was a stunned silence from other competitors, but then Absinth, Liam Caffrey, Cary Taylor and Ryan Randall came in with some fresh and original ideas. Pierre-702284 and Lattice, in particular, surprised Joe with the different ways of approaching the problem.

Joe was surprised that few contestants ran the check SUM(class_size) <= SUM(room_size) so as to see if it is impossible to stuff the classrooms; he was also expecting the ROW_NUMBER() OVER() technique to be used more. However, as more entries came in, it became apparent that the contestants wanted to experiment. Peso enlivened the competition by gently highlighting the flaws in the early submissions on SSC in order to guide contestants towards a better solution. He then created a much better data set (the initial one was far too small) and Ryan and Dennis Allen produced some very slick solutions that became much more linear with increasing data sizes.

In the end, Joe decided to award the prize to Pierre702284. He is the “new kid on the block”; he got there first and really worked on it. Granted there was a lot of feedback from Peso, but he kept at it and cleaned up the code to make sure it was readable. However, an honourable mention must go to Steriod1970 who tried something different and original (goodness of fit scoring) who might have won had he been able to fully carry it out. Last, but not least, is Peso, whose contribution was magnificent.

Tags: , ,

  • 15640 views

  • Rate
    [Total: 10    Average: 3.6/5]
  • Alex K

    can we change less to less or equal?
    let’s replace

    (class_size < room_size)

    with

    (class_size <= room_size)

    What do we need an empty seat in every class for?

  • Peso

    Descending order algorithm #1
    This will give you good performance, using the descending order algorithm. However, since cte’s are not materialized the cteSource is evaluated n times.

    ;WITH cteSource(room_nbr, class_nbr, recID)
    AS (
    SELECT    r.room_nbr,
        
    c.class_nbr,
        
    ROW_NUMBER() OVER (ORDER BY r.room_size DESC, c.class_size DESC) AS recID
    FROM    dbo.Rooms AS r
    INNER JOIN dbo.Classes AS c ON c.class_size &amp;lt;= r.room_size
    ), cteYak(recID, room_nbr, roomPath, class_nbr, classPath, isPresent)
    AS (
    SELECT  recID,
      
    room_nbr,
      
    ‘/’ + CAST(room_nbr AS VARCHAR(MAX)) + ‘/’ AS roomPath,
      
    class_nbr,
      
    ‘/’ + CAST(class_nbr AS VARCHAR(MAX)) + ‘/’ AS classPath,
      
    CAST(0 AS BIGINT)
    FROM  cteSource
    WHERE recID = 1

    UNION ALL

    SELECT  recID,
      
    room_nbr,
      
    CASE isPresent
        
    WHEN 0 THEN roompath + CAST(room_nbr AS VARCHAR(MAX)) + ‘/’
        
    ELSE roompath
      
    END AS roompath,
      
    class_nbr,
      
    CASE isPresent
        
    WHEN 0 THEN classpath + CAST(class_nbr AS VARCHAR(MAX)) + ‘/’
        
    ELSE classpath
      
    END AS classpath,
      
    isPresent
    FROM  (
        
    SELECT    s.recID,
            
    s.room_nbr,
            
    y.roomPath,
            
    s.class_nbr,
            
    y.classpath,
            
    CHARINDEX(‘/’ + CAST(s.room_nbr AS VARCHAR(MAX)) + ‘/’, y.roompath)
             +
    CHARINDEX(‘/’ + CAST(s.class_nbr AS VARCHAR(MAX)) + ‘/’, y.classpath) AS isPresent
        
    FROM    cteSource AS s
        
    INNER JOIN cteYak AS y ON y.recID + 1 = s.recID
      
    ) AS d
    )
    SELECT room_nbr,
    class_nbr
    FROM cteYak
    WHERE  isPresent = 0

  • Peso

    Descending order algorithm #2
    This is a rewrite of #1 using a table variable instead of using a cte for cteSource. This will ensure a linear approach to the Descending Order algorithm.

    — Initialize and find the valid combinations
    DECLARE @Source TABLE(room_nbr CHAR(2), class_nbr CHAR(2), recID INT PRIMARY KEY CLUSTERED)

    INSERT   @Source(room_nbr, class_nbr, recID)
    SELECT   r.room_nbr,
      
    c.class_nbr,
      
    ROW_NUMBER() OVER (ORDER BY r.room_size DESC, c.class_size DESC) AS recID
    FROM   dbo.Rooms AS r
    INNER JOIN  dbo.Classes AS c ON c.class_size &amp;lt;= r.room_size

    — Iterate the possibilities and return the unique answers
    ;WITH cteYak(recID, room_nbr, roomPath, class_nbr, classPath, isPresent)
    AS (
    SELECT  recID,
      
    room_nbr,
      
    ‘/’ + CAST(room_nbr AS VARCHAR(MAX)) + ‘/’ AS roomPath,
      
    class_nbr,
      
    ‘/’ + CAST(class_nbr AS VARCHAR(MAX)) + ‘/’ AS classPath,
      
    CAST(0 AS BIGINT)
    FROM  @Source
    WHERE recID = 1

    UNION ALL

    SELECT  recID,
      
    room_nbr,
      
    CASE isPresent
        
    WHEN 0 THEN roompath + CAST(room_nbr AS VARCHAR(MAX)) + ‘/’
        
    ELSE roompath
      
    END AS roompath,
      
    class_nbr,
      
    CASE isPresent
        
    WHEN 0 THEN classpath + CAST(class_nbr AS VARCHAR(MAX)) + ‘/’
        
    ELSE classpath
      
    END AS classpath,
      
    isPresent
    FROM  (
        
    SELECT    s.recID,
            
    s.room_nbr,
            
    y.roomPath,
            
    s.class_nbr,
            
    y.classpath,
            
    CHARINDEX(‘/’ + CAST(s.room_nbr AS VARCHAR(MAX)) + ‘/’, y.roompath)
             +
    CHARINDEX(‘/’ + CAST(s.class_nbr AS VARCHAR(MAX)) + ‘/’, y.classpath) AS isPresent
        
    FROM    @Source AS s
        
    INNER JOIN cteYak AS y ON y.recID + 1 = s.recID
      
    ) AS d
    )
    SELECT room_nbr,
    class_nbr
    FROM cteYak
    WHERE  isPresent = 0

  • Ryan Randall

    stab #1 – row_number() approach
    ;
    WITH  Rooms
            
    AS (SELECT
                  
    *, row_number() OVER (ORDER BY room_size DESC) AS Precedence
                
    FROM
                  
    Rooms
              
    ) ,
          
    Classes1
            
    AS (SELECT
                  
    c.class_nbr, c.class_size,
                  
    COUNT(*)-row_number() OVER (ORDER BY class_size DESC) AS x
                
    FROM
                  
    Classes c
                  
    INNER JOIN Rooms r
                    
    ON c.class_size<=r.room_size
                
    GROUP BY
                  
    c.class_nbr, c.class_size
              
    ) ,
          
    Classes2
            
    AS (SELECT
                  
    *,
                  
    row_number() OVER (PARTITION BY x ORDER BY class_size DESC) AS y
                
    FROM
                  
    Classes1
              
    ) ,
          
    Classes3
            
    AS (SELECT
                  
    *, row_number() OVER (ORDER BY class_size DESC) AS z
                
    FROM
                  
    Classes2
                
    WHERE
                  
    NOT (x<0
                      
    AND y=1)
               )
      
    SELECT
        
    *
      
    FROM
        
    Rooms a
        
    INNER JOIN Classes3 b
          
    ON a.Precedence=b.z

    First stab: fails 2, 3 and 5; not sure about rules 1 and 4.

  • Cary Taylor

    Simplified SQL Server 2000 solution
    DECLARE  @reserve_space  INT
    SET  
    @reserve_space = 0

    SELECT r.*, c.*
    FROM  rooms  r
    JOIN
    (
    SELECT room_nbr, MAX(class_size) AS class_size
    FROM  rooms
    CROSS JOIN classes
    WHERE  room_size >= class_size + @reserve_space
    GROUP BY room_nbr
    )  rc
    ON   r.room_nbr = rc.room_nbr
    JOIN  classes  c
    ON    rc.class_size = c.class_size

    To resolve the issue whether then condition should be >= or >, I included reserve space. reserve space of 0 equates to >= while reserve space of 1 equates to >. reserve space greater than 1 generalizes the solution.

    The solution is a descending order algorithm that fully takes advantage of the unique constraints on room_size and class_size.

  • Cary Taylor

    User defined function with cross apply solution
    CREATE  FUNCTION  dbo.class_fit
    (@room_nbr VARCHAR(2), @room_size INT, @reserve_space  INT)
    RETURNS  @class_match  TABLE
    (
    class_nbr  VARCHAR(2),
    class_size  INT,
    room_nbr   VARCHAR(2),
    room_size  INT
    )
    AS
    BEGIN
    INSERT INTO  
    @class_match
    SELECT  @room_nbr AS room_nbr, @room_size AS room_size, c.class_nbr, c.class_size
    FROM    classes  c
    JOIN
    (
    SELECT  MAX(class_size)  AS class_size
    FROM    classes
    WHERE   class_size <= @room_size + @reserve_space
    )  cs
    ON      c.class_size = cs.class_size
    RETURN
    END
    GO

    SELECT cf.*
    FROM  rooms  r
    CROSS apply dbo.class_fit(r.room_nbr, r.room_size, 0)  cf
    GO


    To resolve the issue whether then condition should be >= or >, I included reserve space. reserve space of 0 equates to >= while reserve space of 1 equates to >. reserve space greater than 1 generalizes the solution.

    The solution is a descending order algorithm that fully takes advantage of the unique constraints on room_size and class_size. The use of the cross apply requires at least SQL Server 2005.

  • Lattice

    Solution with variable table
    /*this table will contain all posible relations between rooms and classes*/
    DECLARE @paso TABLE(room_nbr CHAR(2) NOT NULL,
            
    class_nbr CHAR(2) NOT NULL,
            
    room_size INTEGER NOT NULL,
            
    class_size INTEGER NOT NULL)

    /*THIS TABLE WILL BE A CONTROL VARIABLE AND IT WILL CONTAIN THE FINAL RESULTSET*/
    DECLARE @FINAL TABLE(room_nbr CHAR(2) NOT NULL,
            
    class_nbr CHAR(2) NOT NULL)

    /*populate the variable with de constrain class_size &lt;= room_size*/
    INSERT INTO @paso(room_nbr,room_size,class_nbr,class_size)
    SELECT rooms.room_nbr, rooms.room_size,class.class_nbr, class.class_size
    FROM Classes class,
    (
    SELECT rooms.room_nbr, rooms.room_size
    FROM Rooms rooms
    ) rooms
    WHERE class.class_size &amp;lt;= rooms.room_size

    WHILE (1=1)
    BEGIN
    –ASSING THE BIGGER ROOM AVAILABLE TO THE BIGGER CLASS
    INSERT INTO @FINAL(class_nbr,room_nbr)
    SELECT f1.class_nbr,F1.room_nbr
    FROM @paso F1 INNER JOIN (
      
    SELECT f1.class_nbr,MAX (f1.room_size) AS room_size
      
    FROM @paso f1 INNER JOIN
      
    (
        
    SELECT p.room_nbr,MAX(p.class_size) AS class_size
        
    FROM @paso p
        
    GROUP BY room_nbr
      
    )f2
      
    ON f1.room_nbr = f2.room_nbr
      
    AND f1.class_size = f2.class_size
      
    GROUP BY f1.class_nbr
    ) F2
    ON f1.class_nbr = f2.class_nbr
    AND f1.room_size = f2.room_size

    –REPEAT TASK UNTIL RELATION SET IS IS EMPTY OR WITH DUPLICATED VALUES
    IF(@@ROWCOUNT = 0)
      
    BREAK

    –DELETE ALL VALUES THAT EXISTS IN THE RESULT SET
    DELETE PASO
    FROM @paso PASO INNER JOIN  @FINAL FINAL
    ON ((PASO.room_nbr = FINAL.room_nbr) OR (PASO.class_nbr = FINAL.class_nbr))  
    END

    SELECT * FROM @FINAL

  • Lattice

    Solution with variable table (Corrected)
    /*this table will contain all posible relations between rooms and classes*/
    DECLARE @paso TABLE(room_nbr CHAR(2) NOT NULL,
            
    class_nbr CHAR(2) NOT NULL,
            
    room_size INTEGER NOT NULL,
            
    class_size INTEGER NOT NULL,
            
    PRIMARY KEY(room_nbr,class_nbr))

    /*THIS TABLE WILL BE A CONTROL VARIABLE AND IT WILL CONTAIN THE FINAL RESULTSET*/
    DECLARE @FINAL TABLE(room_nbr CHAR(2) NOT NULL PRIMARY KEY,
            
    class_nbr CHAR(2) NOT NULL UNIQUE)

    /*populate the variable with de constrain class_size &lt;= room_size*/
    INSERT INTO @paso(room_nbr,room_size,class_nbr,class_size)
    SELECT rooms.room_nbr, rooms.room_size,class.class_nbr, class.class_size
    FROM Classes class, Rooms rooms
    WHERE class.class_size &amp;lt;= rooms.room_size

    WHILE (1=1)
    BEGIN

    –ASSING THE BIGGER ROOM AVAILABLE TO THE BIGGER CLASS
    INSERT INTO @FINAL(class_nbr,room_nbr)
    SELECT f1.class_nbr,F1.room_nbr
    FROM @paso F1 INNER JOIN (
      
    SELECT f1.class_nbr,MAX (f1.room_size) AS room_size
      
    FROM @paso f1 INNER JOIN
      
    (
        
    SELECT p.room_nbr,MAX(p.class_size) AS class_size
        
    FROM @paso p
        
    GROUP BY room_nbr
      
    )f2
      
    ON f1.room_nbr = f2.room_nbr
      
    AND f1.class_size = f2.class_size
      
    GROUP BY f1.class_nbr
    ) F2
    ON f1.class_nbr = f2.class_nbr
    AND f1.room_size = f2.room_size

    –REPEAT TASK UNTIL RELATION SET IS IS EMPTY OR WITH DUPLICATED VALUES
    IF(@@ROWCOUNT = 0)
      
    BREAK

    –DELETE ALL VALUES THAT EXISTS IN THE RESULT SET
    DELETE PASO
    FROM @paso PASO INNER JOIN  @FINAL FINAL
    ON ((PASO.room_nbr = FINAL.room_nbr) OR (PASO.class_nbr = FINAL.class_nbr))  
    END

    SELECT room_nbr,class_nbr
    FROM @FINAL

  • Peso

    Suggestion made by Cary Taylor
    It’s a clever solution, and relies on also class sizes and room sizes are unique.
    Try to add Room 9 with 90 seats to the sample data and run your query again.

  • craigwork

    Matching classes and size
    A quick solution … I’ll see if there is a better. Its inspired vaguely by relational division and some of snodgrasses work , probably one join can be removed, so I’ll work a bit more later …

    SELECT *
    FROM Rooms AS Ra, Classes AS Ca
    WHERE class_size <= room_size
    AND NOT EXISTS ( SELECT *
              
    FROM Rooms AS Rb, Classes AS Cb
              
    WHERE Cb.class_size <= Rb.room_size
                
    AND Ra.room_size > Rb.room_size
                
    AND Ca.class_size = Cb.class_size
            
    )
    ORDER BY room_size, class_size;

  • craigwork

    …. Alternative solution
    Sorry for the double post above, and unformatted sql. An alternative (faster) solution, with fewer joins, and hopefully some formatting. Inspired by Snodgrass on temporal databases p. 161 ff.

    SELECT Ca.class_size, Ra.room_size
    FROM Rooms AS Ra,
        
    Classes AS Ca,
        
    Rooms AS Rb
    WHERE Ca.class_size <= Ra.room_size
    GROUP BY Ca.class_size, Ra.room_size
    HAVING COUNT( CASE
      
    WHEN ( Ca.class_size
                            
    <= Rb.room_size
                                
    AND Ra.room_size
                            
    > Rb.room_size
                  
    )
          
    THEN 1
      
    END
    ) = 0

    ORDER BY Ra.room_size, Ca.class_size;

  • cbuettner

    Dynamic SQL
    /* I guess the “optimal” would be recursive, but to stick with SQL Server 2000 (huh?)  I’d come up with the below one. To avoid recursion, I generate all possible mapping    sets of rooms to classes. Each mapping set may only contain each room once and each class once. When all possible mappings have been determined, it is time to find an    “optimal” solution. This can be done by first sorting (desc) by the number of mappings found (of course we prefer to have all classes assigned) and then sorting by the sum   of open seats in this solution – this one should be minimal to find an optimal solution.*/

    DECLARE @SQL NVARCHAR(4000)
    SET @SQL = (SELECT  TOP 1 Sets FROM (

    SELECT  Sets — Possible solutions (includes invalid ones)
          
    ,LEN(Sets)/9 [Elements] — Nuber of class/room matches – we want to mach as many as possible; 9 is the length of element strings “(cx,rx,xy)”
          
    ,OpenSeats — Number of open seats altogether for all table class combinations in the set.
    FROM (
    SELECT
          
    ISNULL(‘SELECT ”’ + A.class_nbr + ”’ class_nbr,’ + CAST(A.class_size AS CHAR(2)) + ‘ AS class_size, ”’ + A.room_nbr + ”’ AS room_nbr, ‘ + CAST(A.room_size AS CHAR(2)) + ‘ AS room_size, ‘+ CAST(A.room_size A.class_size AS CHAR(2))+ ‘ AS OpenSeats ‘ + CHAR(13) + CHAR(10),)+
          
    ISNULL(‘UNION ALL SELECT ”’ + B.class_nbr + ”’ class_nbr,’ + CAST(B.class_size AS CHAR(2)) + ‘ AS class_size, ”’ + B.room_nbr + ”’ AS room_nbr, ‘ + CAST(B.room_size AS CHAR(2)) + ‘ AS room_size, ‘+ CAST(B.room_size B.class_size AS CHAR(2))+ ‘ AS OpenSeats ‘+ CHAR(13) + CHAR(10),)+
          
    ISNULL(‘UNION ALL SELECT ”’ + C.class_nbr + ”’ class_nbr,’ + CAST(C.class_size AS CHAR(2)) + ‘ AS class_size, ”’ + C.room_nbr + ”’ AS room_nbr, ‘ + CAST(C.room_size AS CHAR(2)) + ‘ AS room_size, ‘+ CAST(C.room_size C.class_size AS CHAR(2))+ ‘ AS OpenSeats ‘+ CHAR(13) + CHAR(10),)+
          
    ISNULL(‘UNION ALL SELECT ”’ + D.class_nbr + ”’ class_nbr,’ + CAST(D.class_size AS CHAR(2)) + ‘ AS class_size, ”’ + D.room_nbr + ”’ AS room_nbr, ‘ + CAST(D.room_size AS CHAR(2)) + ‘ AS room_size, ‘+ CAST(D.room_size D.class_size AS CHAR(2))+ ‘ AS OpenSeats ‘+ CHAR(13) + CHAR(10),)+
          
    ISNULL(‘UNION ALL SELECT ”’ + E.class_nbr + ”’ class_nbr,’ + CAST(E.class_size AS CHAR(2)) + ‘ AS class_size, ”’ + E.room_nbr + ”’ AS room_nbr, ‘ + CAST(E.room_size AS CHAR(2)) + ‘ AS room_size, ‘+ CAST(E.room_size E.class_size AS CHAR(2))+ ‘ AS OpenSeats ‘+ CHAR(13) + CHAR(10),)+
          
    ISNULL(‘UNION ALL SELECT ”’ + F.class_nbr + ”’ class_nbr,’ + CAST(F.class_size AS CHAR(2)) + ‘ AS class_size, ”’ + F.room_nbr + ”’ AS room_nbr, ‘ + CAST(F.room_size AS CHAR(2)) + ‘ AS room_size, ‘+ CAST(F.room_size F.class_size AS CHAR(2))+ ‘ AS OpenSeats ‘+ CHAR(13) + CHAR(10),) Sets
          
    /*calculate the open seats for all rooms in ech set (room-size – class size for each room)*/
    ,ISNULL(A.room_sizeA.class_size,0)
    +
    ISNULL(B.room_sizeB.class_size,0)
    +
    ISNULL(C.room_sizeC.class_size,0)
    +
    ISNULL(D.room_sizeD.class_size,0)
    +
    ISNULL(E.room_sizeE.class_size,0)
    +
    ISNULL(F.room_sizeF.class_size,0) OpenSeats
    FROM
    /* Join the possible scenarios to build the sets
       Each element (one element is one subquery) of a set is a combination of room &amp; class
       Each element may only exist once per set (each room may be only used once and each class
       may only be used once – therefore the Join clause must exclude elements that use a class
       or a room that was already used within the set. Usually we would use the room_nbr &amp; class_nbr,
       but since the sizes are unique, we can also use the size as identifyer.
    */
    (SELECT * FROM Classes, Rooms WHERE class_size < room_size  /*Start with first class (descending) */) A
    LEFT JOIN (SELECT * FROM Classes, Rooms WHERE class_size < room_size) B ON A.room_size <> B.room_size AND A.class_nbr <> B.class_nbr
    LEFT JOIN (SELECT * FROM Classes, Rooms WHERE class_size < room_size) C ON A.room_size <> C.rooom_size AND A.class_nbr <> C.class_nbr
                                    
    AND B.room_size <> C.room_size AND B.class_nbr <> C.class_nbr
    LEFT JOIN (SELECT * FROM Classes, Rooms WHERE class_size < room_size) D ON A.room_size <> D.room_size AND A.class_nbr <> D.class_nbr
          
    AND B.room_size <> D.room_size AND B.class_nbr <> D.class_nbr
          
    AND C.room_size <> D.room_size AND C.class_nbr <> D.class_nbr
    LEFT JOIN (SELECT * FROM Classes, Rooms WHERE class_size < room_size) E ON A.room_size <> E.room_size AND A.class_nbr <> E.class_nbr
          
    AND B.room_size <> E.room_size AND B.class_nbr <> E.class_nbr
          
    AND C.room_size <> E.room_size AND C.class_nbr <> E.class_nbr
          
    AND D.room_size <> E.room_size AND D.class_nbr <> E.class_nbr
    LEFT JOIN (SELECT * FROM Classes, Rooms WHERE class_size < room_size) F ON A.room_size <> F.room_size AND A.class_nbr <> F.class_nbr
          
    AND B.room_size <> F.room_size AND B.class_nbr <> F.class_nbr
          
    AND C.room_size <> F.room_size AND C.class_nbr <> F.class_nbr
          
    AND D.room_size <> F.room_size AND D.class_nbr <> F.class_nbr
          
    AND E.room_size <> F.room_size AND E.class_nbr <> F.class_nbr
    ) Sets
    ) AllSolutions
    ORDER BY Elements DESC — We want the most combinations as many rooms with as many classes
            
    ,OpenSeats ASC — We want as little as possbible lost seats[/code]
    )
    PRINT @SQL
    EXEC (@SQL + ‘ ORDER BY 1’)

  • Regan Wick

    Classes 2 Rooms
    I sent this solution to Stephen Forte after he presented this problem at Tech Ed.

    SELECT
      
    Classes.class_nbr
    ,Classes.class_size
    ,RoomAssignments.room_nbr
    ,RoomAssignments.room_size
    FROM
    Classes LEFT OUTER JOIN
    (
    SELECT *
    FROM
      
    (
      
    SELECT
          
    AllData.*
         ,
    ROW_NUMBER() OVER
          
    (
            
    PARTITION BY
                
    room_nbr
            
    ORDER BY
                
    ROOM_RANK
          
    ) AS ROOM_ASSIGMNET
      
    FROM
        
    (
        
    SELECT
            
    ScheduleData.*
           ,
    ROW_NUMBER() OVER
            
    (
              
    PARTITION BY
                  
    class_nbr
              
    ORDER BY
                  
    ROOM_RANK
            
    ) AS CLASS_ASSIGMNET
        
    FROM
          
    (
          
    SELECT
              
    Rooms.*
             ,
    Classes.*
             ,
    ROW_NUMBER() OVER
              
    (
                
    PARTITION BY
                    
    room_nbr
                
    ORDER BY
                    
    class_size  DESC
                  
    ,class_nbr
              
    ) AS ROOM_RANK
          
    FROM
            
    Classes INNER JOIN
            
    Rooms ON class_size <= room_size
          
    ) ScheduleData
        
    ) AllData
      
    WHERE
        
    CLASS_ASSIGMNET = 1
      
    ) AllData2
    WHERE
      
    ROOM_ASSIGMNET  = 1
    ) RoomAssignments ON Classes.class_nbr = RoomAssignments.class_nbr

  • craigwork

    …. thinking …
    ‘Pretend’ that all classes are happily in a room, and it is the type of weirdo-quantum Universe where all combinations of rooms and classes can simultaneously exist, yet (valid combinations) only materialise when one asks (and receives an answer to) … ‘Is there a room smaller than the one I am in, into which I can fit?’

    (My thoughts were roughly along those sort of lines 🙂 )

  • Anonymous

    Class Scheduling problem
    If you want to solve this for an entire highschool with teachers, student, classrooms, courses and so on.. best to start randomly and use special optimization algorithms. Had this timetabling problem as my graduation task. Never thought about solving this in sql 🙂
    Wonder if we include time-depended attributes like when the teacher got sick and needed replacement.

    Nice question.

    greets

  • centaur

    Classroom Sceduling
    I have not done any testing of scale, but I am sure that is the key to having a truly well thought out solution.

    SELECT
        r.room_nbr,
        c.class_nbr,
        (r.room_size c.class_size) AS empty_seats
    FROM
        Rooms AS r
    INNER JOIN
        Classes AS c ON c.class_size < r.room_size
    INNER JOIN (
        SELECT
            class_nbr,
            min(room_size class_size) AS min_empty_seats
         FROM
            Rooms
         INNER JOIN
            Classes ON class_size < room_size
         GROUP BY
            class_nbr
        ) AS min_size
        ON        min_size.class_nbr = c.class_nbr
        AND min_size.min_empty_seats = (r.room_size – c.class_size)

  • Paul Cappelluzzo

    Class Scheduling answer
    I feel like I must be missing something, because my answer is too simple. My thinking is that once you match rooms to classes using the filter of room size > class size, then you just need to pair them by the closest size fit, so that a small class doesn’t get paired with large room, thus preventing a large class from using that room. As long as the sizes are unique within their group (room or class), then there is no need to arbitraily resolve mutliple “closest fits” to a single pairing for a given room or class.

    Here is my solution using CTEs, but one could easily replace each instance of the CTE (PossibleMatches) with the actual select statement to get a simple, portable, if redundant, solution:

    WITH PossibleMatches(room_nbr, class_nbr, SizeDifference) AS
    (  
    SELECT
    R.room_nbr,
    C.class_nbr,
    SizeDifference = R.room_size C.class_size
    FROM Rooms R
    INNER JOIN Classes C
    ON  R.room_size > C.class_size
    )
    SELECT
    PM.class_nbr,
    PM.room_nbr
    FROM PossibleMatches PM
    INNER JOIN
    ( SELECT
      
    room_nbr,
      
    MinSizeDifference = MIN(SizeDifference)
      
    FROM PossibleMatches
      
    GROUP BY room_nbr
    ) RoomAgg1
    ON  PM.room_nbr = RoomAgg1.room_nbr AND
      
    PM.SizeDifference = RoomAgg1.MinSizeDifference
    ORDER BY PM.class_nbr

  • centaur

    Inspired to remove a sub-query
    I knew there had to be a simpler way than creating a full 2nd set of the classes and rooms.  By re-joining the rooms and limiting them to only those that have a smaller size I know that the rooms “r” that do not have an overlap with rooms “x” are the ones that will have the fewest empty seats.

    SELECT
        c.class_nbr,
        r.room_nbr,
        c.class_size,
        r.room_size,
        (r.room_sizec.class_size) empty_seats
    FROM
        Classes c
    INNER JOIN
        /* inclusion set: all rooms that meet the criteria */
        Rooms r ON c.class_size < r.room_size
    LEFT JOIN
        /* exclusion set: overlaps the members we do not want to include */
        Rooms x ON c.class_size < x.room_size
                   AND x.room_size < r.room_size
    WHERE
        /* only those class + room combinations that our exclusion set does not overlap */
        x.room_nbr IS NULL
    ORDER BY
         1, 2

  • Raj Samrat

    Celko’s SQL Stumper: The Class Scheduling Problem
    DECLARE @T_Rooms TABLE

    (room_nbr CHAR(2) NOT NULL PRIMARY KEY,

    room_size INTEGER NOT NULL

    CHECK (room_size > 0));

    DECLARE @T_Classes TABLE

    (class_nbr CHAR(2) NOT NULL PRIMARY KEY,

    class_size INTEGER NOT NULL

    CHECK (class_size > 0));

    INSERT INTO @T_Classes (class_nbr, class_size) VALUES(‘c1’, 80)
    INSERT INTO @T_Classes (class_nbr, class_size) VALUES(‘c2’, 70)
    INSERT INTO @T_Classes (class_nbr, class_size) VALUES(‘c3’, 65)
    INSERT INTO @T_Classes (class_nbr, class_size) VALUES (‘c4’, 55)
    INSERT INTO @T_Classes (class_nbr, class_size) VALUES (‘c5’, 50)
    INSERT INTO @T_Classes (class_nbr, class_size) VALUES (‘c6’, 40)

    INSERT INTO @T_Rooms (room_nbr, room_size)VALUES (‘r1’, 70)
    INSERT INTO @T_Rooms (room_nbr, room_size)VALUES (‘r2’, 40)
    INSERT INTO @T_Rooms (room_nbr, room_size)VALUES (‘r3’, 50)
    INSERT INTO @T_Rooms (room_nbr, room_size)VALUES (‘r4’, 85)
    INSERT INTO @T_Rooms (room_nbr, room_size)VALUES (‘r5’, 30)
    INSERT INTO @T_Rooms (room_nbr, room_size)VALUES (‘r6’, 65)
    INSERT INTO @T_Rooms (room_nbr, room_size)VALUES (‘r7’, 55)

    –select * from @T_Classes
    –select * from @T_Rooms

    /*select C.class_nbr,R.room_nbr,R.Room_Size,C.class_size,(R.room_size-C.class_size)as diff
    from @T_Classes C,@T_Rooms R
    where (R.room_size-C.class_size)> 0*/

    select T1.class_nbr,T3.room_nbr, T3.Room_size,T1.class_size,t2.Diff
    from @T_Classes T1 INNER JOIN (

    select C.class_nbr,R.room_nbr,MIN((R.room_size-C.class_size))AS DIFF
    from @T_Classes C,@T_Rooms R
    where (R.room_size-C.class_size)> 0
    group by C.class_nbr,R.room_nbr
    ) T2
    ON T1.class_nbr = T2.class_nbr
    INNER JOIN @T_Rooms T3
    ON T2.room_nbr = T3.room_nbr
    WHERE EXISTS (SELECT 1
    from (select R.room_nbr,MIN((R.room_size-C.class_size))AS DIFF
    from @T_Classes C,@T_Rooms R
    where (R.room_size-C.class_size)> 0
    group by R.room_nbr)S
    where s.room_nbr=T3.room_nbr
    and s.diff=T2.diff
    )