Recent PostsRecent Posts Popular TopicsPopular Topics
 Home Search Members Calendar Who's On

 Celko's SQL Stumper: The Class Scheduling Problem Rate Topic Display Mode Topic Options
Author
 Message
 Posted Tuesday, January 26, 2010 3:24 PM
 SSCrazy Group: General Forum Members Last Login: Tuesday, April 14, 2015 6:45 AM Points: 2,403, Visits: 3,431
 David, your solution has the same limitations as Pierre's.Add two new rooms {r8, r9} with {800, 900} seats, and add two new classes {c8, c9} with {5, 10} students and run your query again. N 56°04'39.16"E 12°55'05.25"
Post #854011
 Posted Tuesday, January 26, 2010 3:28 PM
 SSCrazy Group: General Forum Members Last Login: Tuesday, April 14, 2015 6:45 AM Points: 2,403, Visits: 3,431
 No, I am not just complaining. I have another suggestion herehttp://weblogs.sqlteam.com/peterl/archive/2010/01/23/Celko-Stumper---The-Class-Scheduling-Problem.aspxOr as a "one-query"-solution...DECLARE @HowManySeatsFree INT = 0 -- Set to zero for maximum seating, and to 1 for letting in late pupils.;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 <= r.room_size - @HowManySeatsFree), 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 cteSource 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 cteSource AS s INNER JOIN cteYak AS y ON y.recID + 1 = s.recID ) AS d)SELECT room_nbr, class_nbrFROM cteYakWHERE isPresent = 0 -- Only present the combination never taken/found beforeOPTION (MAXRECURSION 0) -- Allow up to 32767 possible combinations. N 56°04'39.16"E 12°55'05.25"
Post #854014
 Posted Tuesday, January 26, 2010 3:50 PM
 SSCommitted Group: General Forum Members Last Login: Today @ 5:33 AM Points: 1,945, Visits: 3,497
 I am surprised by two things here: 1) Nobody bothered to see if SUM(class_size) <= SUM(room_size) so we know if it is impossible to stuff the classrooms. 2) I was expecting the ROW_NUMBER() OVER() to be used more.3) I was expecting someone to look up the solutoins in SQL FOR SMARTIES and re-wroite them with new features and CTEs. Books in Celko Series for Morgan-Kaufmann PublishingAnalytics and OLAP in SQL Data and Databases: Concepts in Practice Data, Measurements and Standards in SQLSQL for SmartiesSQL Programming Style SQL Puzzles and Answers Thinking in SetsTrees and Hierarchies in SQL
Post #854024
 Posted Tuesday, January 26, 2010 3:58 PM
 SSCrazy Group: General Forum Members Last Login: Tuesday, April 14, 2015 6:45 AM Points: 2,403, Visits: 3,431
 Joe Celko (1/26/2010)I am surprised by two things here: 1) Nobody bothered to see if SUM(class_size) <= SUM(room_size) so we know if it is impossible to stuff the classrooms. 2) I was expecting the ROW_NUMBER() OVER() to be used more.3) I was expecting someone to look up the solutoins in SQL FOR SMARTIES and re-wroite them with new features and CTEs. So you came up with this stumper to sell more books? Which two of the three things surprised you? N 56°04'39.16"E 12°55'05.25"
Post #854025
 Posted Wednesday, January 27, 2010 2:28 AM
 SSC Rookie Group: General Forum Members Last Login: Friday, June 6, 2014 4:34 AM Points: 40, Visits: 143
 Attempt #2.1: Descending order algorithmWITH AllocationOrder AS ( SELECT class_nbr, class_size, class_alloc_order = DENSE_RANK() OVER (ORDER BY class_size DESC, class_nbr), room_nbr, room_size, room_alloc_order = DENSE_RANK() OVER (ORDER BY room_size DESC, room_nbr) FROM Classes, Rooms WHERE class_size <= room_size ),Priority AS ( SELECT room_alloc_order, class_room_priority = ROW_NUMBER() OVER (PARTITION BY room_alloc_order ORDER BY class_alloc_order), class_nbr, class_size, room_nbr, room_size FROM AllocationOrder WHERE room_alloc_order <= class_alloc_order )SELECT c.class_nbr, c.class_size, p.room_nbr, p.room_sizeFROM Classes c LEFT JOIN Priority p ON c.class_nbr = p.class_nbr AND p.class_room_priority = 1ORDER BY c.class_size DESC
Post #854242
 Posted Wednesday, January 27, 2010 3:54 AM
 SSC Rookie Group: General Forum Members Last Login: Friday, November 7, 2014 11:31 PM Points: 26, Visits: 63
 1. Always better to start with a blank sheet, then you really own the problem.2. I understood lack of obscurity, portability and backward compatibility were important here.Swe's comments are interesting. I didn't deal with temporal contention because it didn't appear to be an issue from the problem definition. If it is to be dealt with then the possibility that some classes will not get a room has to be dealt with.I like the vacant thresholding idea that some of the contributors have included.I will see can I take a look at this again before the deadline.
Post #854272
 Posted Wednesday, January 27, 2010 4:40 AM
 SSCrazy Group: General Forum Members Last Login: Tuesday, April 14, 2015 6:45 AM Points: 2,403, Visits: 3,431
 pierre-702284 (1/27/2010)Attempt #2: Ascending order algorithmAdd a room r8 with 48 seats.pierre-702284 (1/27/2010)Attempt #2: Descending order algorithmAdd a class c9 with 75 students. N 56°04'39.16"E 12°55'05.25"
Post #854292
 Posted Wednesday, January 27, 2010 4:47 AM
 SSC Rookie Group: General Forum Members Last Login: Friday, June 6, 2014 4:34 AM Points: 40, Visits: 143
 Yeah, sorry, I noticed that mistake and I've amended my code. Please try again!
Post #854295
 Posted Wednesday, January 27, 2010 5:23 AM
 SSC Rookie Group: General Forum Members Last Login: Friday, June 6, 2014 4:34 AM Points: 40, Visits: 143
 Attempt #3 - Final version, I promise!!Descending order algorithmSELECT c.class_nbr, c.class_size, s3.room_nbr, s3.room_sizeFROM Classes c LEFT JOIN ( SELECT *, class_priority = ROW_NUMBER() OVER (PARTITION BY class_alloc_order ORDER BY room_size DESC, room_nbr) FROM ( SELECT *, room_priority = ROW_NUMBER() OVER (PARTITION BY room_alloc_order ORDER BY class_alloc_order) FROM ( SELECT class_nbr, class_alloc_order = DENSE_RANK() OVER (ORDER BY class_size DESC, class_nbr), room_nbr, room_size, room_alloc_order = DENSE_RANK() OVER (ORDER BY room_size DESC, room_nbr) FROM Classes, Rooms WHERE class_size <= room_size ) s1 WHERE room_alloc_order <= class_alloc_order ) s2 WHERE room_priority = 1 ) s3 ON c.class_nbr = s3.class_nbr AND s3.class_priority = 1ORDER BY c.class_size DESC, c.class_nbr
Post #854303
 Posted Wednesday, January 27, 2010 8:00 AM
 SSC Rookie Group: General Forum Members Last Login: Thursday, February 2, 2012 7:24 AM Points: 30, Visits: 109
 I was not aware that the definition of the problem intended to handle collisions. I assumed the reason for making the class and room sized unique was to avoid that in the solution. Obviously, a first fit solution will have collisions where the sizes are such that they meet the criteria. That certainly would make for a more involved solution. Is that actually the scope of this problem?
Post #854410

 Permissions