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.