Click here to monitor SSC
SQLServerCentral is supported by Red Gate Software Ltd.
 
Log in  ::  Register  ::  Not logged in
 
 
 
        
Home       Members    Calendar    Who's On


Add to briefcase «««45678

Celko's SQL Stumper: The Class Scheduling Problem Expand / Collapse
Author
Message
Posted Monday, February 08, 2010 1:37 PM


Old Hand

Old HandOld HandOld HandOld HandOld HandOld HandOld HandOld Hand

Group: General Forum Members
Last Login: Monday, April 14, 2014 5:08 AM
Points: 331, Visits: 1,356
RyanRandall (2/8/2010)
Non-duplicate test data gives 962 rows and a 'fill factor' of 97.77%. I think these are optimal.

I think they are too, I've done a test of the amount of space in unallocated rooms and unallocated classes left for your solution and mine and they both leave the same amount of space in classes not allocated and rooms not allocated.
Only your's is many times faster.

RyanRandall's solution
----stab #2, without using CTEs or the new WINDOW functions - works whether rooms and classes have duplicate sizes or not
----could we improve this with any indexes or tweaks?

--classes to allocate
CREATE TABLE #Classes1 (Precedence INT IDENTITY(1, 1) PRIMARY KEY, class_nbr CHAR(5), class_size INTEGER)
INSERT INTO #Classes1
SELECT * FROM dbo.Classes WHERE class_size <= (SELECT MAX(room_size) FROM dbo.Rooms)
ORDER BY class_size DESC

CREATE TABLE #Classes2 (Precedence INT IDENTITY(1, 1), class_nbr CHAR(5), class_size INTEGER)
INSERT #Classes2
SELECT class_nbr, class_size FROM #Classes1 WHERE Precedence NOT IN ( --could not exists, except or left join perform better?
SELECT MIN(Precedence) AS Precedence FROM ( --unallocated classes
SELECT c.class_nbr, c.class_size, c.Precedence, COUNT(*)-c.Precedence AS ClassAllocationOffset
FROM #Classes1 c INNER JOIN dbo.Rooms r ON c.class_size <= r.room_size
GROUP BY c.class_nbr, c.class_size, c.Precedence) a
WHERE ClassAllocationOffset < 0
GROUP BY ClassAllocationOffset)
ORDER BY class_size DESC
--/

--rooms to allocate
CREATE TABLE #Rooms1 (Precedence INT IDENTITY(1, 1) PRIMARY KEY, room_nbr CHAR(5), room_size INTEGER)
INSERT INTO #Rooms1
SELECT * FROM dbo.Rooms WHERE room_size >= (SELECT MIN(class_size) FROM dbo.Classes)
ORDER BY room_size

CREATE TABLE #Rooms2 (Precedence INT IDENTITY(1, 1) PRIMARY KEY, room_nbr CHAR(5), room_size INTEGER)
INSERT #Rooms2
SELECT room_nbr, room_size FROM #Rooms1 WHERE Precedence NOT IN (
SELECT MIN(Precedence) AS Precedence FROM ( --unallocated rooms
SELECT r.room_nbr, r.room_size, r.Precedence, COUNT(*)-r.Precedence AS RoomAllocationOffset
FROM #Rooms1 r INNER JOIN dbo.Classes c ON r.room_size >= c.class_size
GROUP BY r.room_nbr, r.room_size, r.Precedence) a
WHERE RoomAllocationOffset < 0
GROUP BY RoomAllocationOffset)
ORDER BY room_size DESC
--/

--allocations
SELECT *, room_size-class_size AS seats_remaining
FROM #Rooms2 r
INNER JOIN #Classes2 c ON r.Precedence = c.Precedence
--/
-- Unallocated rooms
SELECT SUM(r.room_size) UnallocatedRoomSpace
FROM (
SELECT room_size,room_nbr, room_size-class_size AS seats_remaining
FROM #Rooms2 r
INNER JOIN #Classes2 c ON r.Precedence = c.Precedence
) A
RIGHT JOIN rooms r ON r.room_nbr = A.room_nbr
WHERE A.room_nbr IS NULL

-- Unallocated classes
SELECT SUM(c.class_size) UnallcatedClassSpace
FROM (
SELECT class_size,c.class_nbr, room_size-class_size AS seats_remaining
FROM #Rooms2 r
INNER JOIN #Classes2 c ON r.Precedence = c.Precedence
) A
RIGHT JOIN classes c ON c.class_nbr = A.class_nbr
WHERE A.class_nbr IS NULL

--fill factor
SELECT 1.0*SUM(class_size)/SUM(room_size) AS [FillFactor]
FROM #Rooms2 r INNER JOIN #Classes2 c ON r.Precedence = c.Precedence
--
GO

--tidy up
DROP TABLE #Classes1
DROP TABLE #Classes2
DROP TABLE #Rooms1
DROP TABLE #Rooms2
--/
----/

My solution:
CREATE TABLE #Allocated (room_nbr CHAR(5),class_nbr CHAR(5),PRIMARY KEY (room_nbr),UNIQUE (class_nbr))
DECLARE myCursor CURSOR LOCAL FORWARD_ONLY FAST_FORWARD READ_ONLY
FOR SELECT R.room_nbr, C.class_nbr
FROM Classes C
INNER JOIN Rooms R ON C.class_size <= R.room_size
ORDER BY R.room_size - C.class_size

DECLARE @room_nbr CHAR(5), @class_nbr CHAR(5)
OPEN myCursor
FETCH NEXT FROM myCursor INTO @room_nbr, @class_nbr
WHILE @@FETCH_STATUS = 0 BEGIN
IF NOT EXISTS(SELECT 1
FROM #Allocated A
WHERE A.class_nbr = @class_nbr)
AND NOT EXISTS(SELECT 1
FROM #Allocated A
WHERE A.room_nbr = @room_nbr)
INSERT INTO #Allocated (room_nbr, class_nbr) VALUES (@room_nbr,@class_nbr)
FETCH NEXT FROM myCursor INTO @room_nbr, @class_nbr
END
CLOSE myCursor
DEALLOCATE myCursor

SELECT C.class_nbr, R.room_nbr, C.class_size, R.room_size, IsNull(R.room_size,0)-IsNull(C.class_size,0) free_space
FROM #Allocated A
INNER JOIN Classes C ON C.class_nbr = A.class_nbr
INNER JOIN Rooms R ON R.room_nbr = A.room_nbr
ORDER BY R.room_nbr

SELECT SUM(A.room_size) UnallocatedRoomSpace
FROM (
SELECT C.class_nbr, R.room_nbr, C.class_size, R.room_size, IsNull(R.room_size,0)-IsNull(C.class_size,0) free_space
FROM #Allocated A
RIGHT JOIN Classes C ON C.class_nbr = A.class_nbr
FULL JOIN Rooms R ON R.room_nbr = A.room_nbr
WHERE C.class_nbr IS NULL
) A


SELECT SUM(A.class_size) UnallcatedClassSpace
FROM (
SELECT C.class_nbr, R.room_nbr, C.class_size, R.room_size, IsNull(R.room_size,0)-IsNull(C.class_size,0) free_space
FROM #Allocated A
RIGHT JOIN Classes C ON C.class_nbr = A.class_nbr
FULL JOIN Rooms R ON R.room_nbr = A.room_nbr
WHERE R.room_nbr IS NULL
) A
DROP TABLE #Allocated

Post #862041
Posted Sunday, February 21, 2010 12:56 PM


Mr or Mrs. 500

Mr or Mrs. 500Mr or Mrs. 500Mr or Mrs. 500Mr or Mrs. 500Mr or Mrs. 500Mr or Mrs. 500Mr or Mrs. 500Mr or Mrs. 500

Group: General Forum Members
Last Login: 2 days ago @ 11:26 AM
Points: 561, Visits: 2,415
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 was 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 honorable 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.

Joe Celko and Phil Factor



Best wishes,

Phil Factor
Simple Talk
Post #869897
Posted Sunday, February 21, 2010 1:37 PM


SSCrazy

SSCrazySSCrazySSCrazySSCrazySSCrazySSCrazySSCrazySSCrazy

Group: General Forum Members
Last Login: Monday, April 14, 2014 3:07 PM
Points: 2,382, Visits: 3,369
Congratulations Pierre!



N 56°04'39.16"
E 12°55'05.25"
Post #869912
Posted Tuesday, February 23, 2010 9:15 AM
SSC Rookie

SSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC Rookie

Group: General Forum Members
Last Login: Friday, December 06, 2013 7:37 AM
Points: 37, Visits: 142
Wow! Thanks all! I look forward to the next stumper :o)
Post #871230
« Prev Topic | Next Topic »

Add to briefcase «««45678

Permissions Expand / Collapse