Thinking outside the box

Patron Saint of Lost Yaks
posts - 203, comments - 734, trackbacks - 4

My Links

Advertisement

News

Archives

Post Categories

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 ]

Feedback

Gravatar

# re: Celko Stumper - The Class Scheduling Problem

I see you went for the (class_size <= room_size) rather than the (class_size < room_size) T-JOIN. Can you put in some commentary? Why did you put an ORDER BY on an INSERT INTO Statement? I thinhk you are the first answer, by the way.
1/23/2010 11:02 PM | Joe Celko
Gravatar

# re: Celko Stumper - The Class Scheduling Problem

I did put an ORDER BY to ensure matches between class size and room size are done in "proper" order because of the nature of CTE.
The recID value holds a "ticket" for which order to check combinations.
1/24/2010 8:01 AM | Peso
Gravatar

# re: Celko Stumper - The Class Scheduling Problem

Oh, and the REASON for using ORDER BY is to simulate a MERGE JOIN becuase I believe this task will be faster when items are pre-sorted, much like a MERGE JOIN need to.
1/24/2010 8:05 AM | Peso
Gravatar

# re: Celko Stumper - The Class Scheduling Problem

Oh, and the REASON for using ORDER BY is to simulate a MERGE JOIN becuase I believe this task will be faster when items are pre-sorted, much like a MERGE JOIN need to. It also makes sure I start with the largest class and end with the smallest class.
1/24/2010 8:10 AM | Peso
Gravatar

# re: Celko Stumper - The Class Scheduling Problem

Hmmmm. looks eerily familiar.

Always enjoy checking this blog.

All the best, Charlie.
1/25/2010 4:39 PM | Transact Charlie
Gravatar

# re: Celko Stumper - The Class Scheduling Problem

Just spotted this one... here is mine...
[code]
--------------------------------------------------------------------------
-- build a results table
--------------------------------------------------------------------------

CREATE TABLE results
(
id INT IDENTITY(0,1) PRIMARY KEY,
class_nbr CHAR(2),
class_size INT,
room_nbr CHAR(2),
room_size INT
)

INSERT results
SELECT
class_nbr,
class_size,
room_nbr,
room_size
FROM
Classes c
JOIN Rooms r ON r.room_size >= c.class_size

--------------------------------------------------------------------------
--build a function to find the min unused room size
--------------------------------------------------------------------------
GO
CREATE FUNCTION dbo.udfGetMinUnusedRoomsize (@id INT, @class_nbr CHAR(2))
RETURNS INT
AS
BEGIN
DECLARE @room_size int;

SELECT @room_size = MIN(room_size)
FROM results
WHERE class_nbr = @class_nbr AND room_nbr NOT IN (SELECT room_nbr WHERE id < @id)

RETURN @room_size
END
GO

--------------------------------------------------------------------------
--result
--------------------------------------------------------------------------

SELECT
c.class_nbr,
c.class_size,
r.room_nbr,
r.room_size
FROM
Classes c
JOIN
(
SELECT
c.class_nbr,
MIN(dbo.udfGetMinUnusedRoomsize(c.id, c.class_nbr)) AS min_room_size
FROM
results c
GROUP BY
c.class_nbr
) d ON d.class_nbr = c.class_nbr
JOIN Rooms r ON r.room_size = d.min_room_size
ORDER BY c.class_size DESC

--------------------------------------------------------------------------
--clean up
--------------------------------------------------------------------------

DROP TABLE results
DROP FUNCTION dbo.udfGetMinUnusedRoomsize


[/code]
2/24/2010 6:19 AM | ehorn
Comments have been closed on this topic.

Powered by:
Powered By Subtext Powered By ASP.NET