Thinking outside the box

Celko Stumper - The Class Scheduling Problem

Joe Celko has posted a new Stumper - The Class Scheduling Problem
here http://www.simple-talk.com/sql/t-sql-programming/celkos-sql-stumper-the-class-scheduling-problem/

Here is one suggestion to solve the problem. It's linear in time so it should be very fast. It's based on the "Descending order" approach, and the "paths" columns are used to store valid room and classes.

-- Initialize and find the valid combinations
DECLARE  @HowManySeatsFree INT = 0 -- Set to zero for maximum seating, and to 1 for letting in late pupils.

DECLARE  @Source TABLE
        (
            room_nbr CHAR(2),
            class_nbr CHAR(2),
            recID INT IDENTITY(1, 1) PRIMARY KEY CLUSTERED
        )

INSERT      @Source
            (
                room_nbr,
                class_nbr
            )
SELECT      r.room_nbr,
            c.class_nbr
FROM        dbo.Rooms AS r
INNER JOIN  dbo.Classes AS c ON c.class_size <= r.room_size - @HowManySeatsFree
ORDER BY    r.room_size DESC,
            c.class_size DESC

-- 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, -- List of taken rooms
            class_nbr,
            '/' + CAST(class_nbr AS VARCHAR(MAX)) + '/' AS classPath, -- List of taken classes
            CAST(0 AS BIGINT)
    FROM    @Source
    WHERE   recID = 1

    UNION ALL

    SELECT      recID,
                room_nbr,
                CASE isPresent -- If room never encountered before (isPresent=0), take it!
                    WHEN 0 THEN roompath + CAST(room_nbr AS VARCHAR(MAX)) + '/'
                    ELSE roompath
                END AS roompath,
                class_nbr,
                CASE isPresent -- If class never encountered before (isPresent=0), take it!
                    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 -- See if room or class is already taken. If so, isPresent is greater than 0, otherwise it will be 0.
                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 -- Only present the combination never taken/found before
OPTION  (MAXRECURSION 0) -- Allow up to 32767 possible combinations.

Print | posted on Saturday, January 23, 2010 1:31 PM | Filed Under [ Optimization SQL Server 2008 Algorithms SQL Server 2005 SQL Server 2000 ]