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 12345»»»

Celko's SQL Stumper: The Class Scheduling Problem Expand / Collapse
Author
Message
Posted Saturday, January 23, 2010 9:26 PM


SSCommitted

SSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommitted

Group: General Forum Members
Last Login: Tuesday, January 15, 2013 11:11 AM
Points: 1,945, Visits: 2,782
Comments posted to this topic are about the item Celko's SQL Stumper: The Class Scheduling Problem

Books in Celko Series for Morgan-Kaufmann Publishing
Analytics and OLAP in SQL
Data and Databases: Concepts in Practice
Data, Measurements and Standards in SQL
SQL for Smarties
SQL Programming Style
SQL Puzzles and Answers
Thinking in Sets
Trees and Hierarchies in SQL
Post #852673
Posted Monday, January 25, 2010 5:33 AM
SSC Rookie

SSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC Rookie

Group: General Forum Members
Last Login: Wednesday, October 09, 2013 2:56 AM
Points: 25, Visits: 58
Hi,

My approach is to resolve the requirement to an expression on room sets, smaller_room_size < class_size < bigger_room_size, i.e. the complete set of those rooms that are smaller than the class size joined (cross join) with the set of those rooms that are bigger than the class size.

Then, for each class size (group by) get the biggest room that is smaller (max) and the smallest room that is bigger (min). Join this back to the expression-based set of candidates and that's it.

Regards

Liam Caffrey


CREATE TABLE Rooms
(
room_nbr CHAR(2) NOT NULL PRIMARY KEY
,room_size INTEGER NOT NULL CHECK (room_size > 0)
)

CREATE TABLE Classes
(
class_nbr CHAR(2) NOT NULL PRIMARY KEY
,class_size INTEGER NOT NULL CHECK (class_size > 0)
)

INSERT INTO Classes (class_nbr, class_size) VALUES ('c1', 80)
INSERT INTO Classes (class_nbr, class_size) VALUES ('c2', 70)
INSERT INTO Classes (class_nbr, class_size) VALUES ('c3', 65)
INSERT INTO Classes (class_nbr, class_size) VALUES ('c4', 55)
INSERT INTO Classes (class_nbr, class_size) VALUES ('c5', 50)
INSERT INTO Classes (class_nbr, class_size) VALUES ('c6', 40)

INSERT INTO Rooms (room_nbr, room_size) VALUES ('r1', 70)
INSERT INTO Rooms (room_nbr, room_size) VALUES ('r2', 40)
INSERT INTO Rooms (room_nbr, room_size) VALUES ('r3', 50)
INSERT INTO Rooms (room_nbr, room_size) VALUES ('r4', 85)
INSERT INTO Rooms (room_nbr, room_size) VALUES ('r5', 30)
INSERT INTO Rooms (room_nbr, room_size) VALUES ('r6', 65)
INSERT INTO Rooms (room_nbr, room_size) VALUES ('r7', 55)

-- Resolve the requirement to an expression on room sets, smaller_room_size < class_size < bigger_room_size
-- i.e. the set of those rooms that are smaller than the class size joined
-- with the set of those rooms that are bigger than the class size
-- Straight away the solution is evident...
SELECT *
FROM Rooms a
CROSS JOIN
Classes b
CROSS JOIN
Rooms c
WHERE a.room_size < b.class_size
AND c.room_size > b.class_size
ORDER BY b.class_size DESC, a.room_size DESC, c.room_size ASC

-- For each class size get the biggest room that is smaller and the smallest room that is bigger...
SELECT MAX (a.room_size) AS just_too_small_room_size
,b.class_size
,MIN (c.room_size) AS just_too_big_room_size
FROM Rooms a
CROSS JOIN
Classes b
CROSS JOIN
Rooms c
WHERE a.room_size < b.class_size
AND c.room_size > b.class_size
GROUP BY b.class_size

-- ... and join it back to the solution candidates set, et voila...
SELECT y.class_nbr AS class_nbr_requiring_room
,y.class_size AS class_size_requiring_room
,y.bigger_room_nbr AS best_fitting_room_nbr
,y.bigger_room_size AS best_fitting_room_capacity
FROM (
SELECT MAX (a.room_size) AS just_too_small_room_size
,b.class_size
,MIN (c.room_size) AS just_too_big_room_size
FROM Rooms a
CROSS JOIN
Classes b
CROSS JOIN
Rooms c
WHERE a.room_size < b.class_size
AND c.room_size > b.class_size
GROUP BY b.class_size
) x
JOIN
(
SELECT a.room_nbr AS smaller_room_nbr
,a.room_size AS smaller_room_size
,b.class_nbr
,b.class_size
,c.room_nbr AS bigger_room_nbr
,c.room_size AS bigger_room_size
FROM Rooms a
CROSS JOIN
Classes b
CROSS JOIN
Rooms c
WHERE a.room_size < b.class_size
AND c.room_size > b.class_size
) y
ON x.just_too_small_room_size = y.smaller_room_size
AND x.class_size = y.class_size
AND x.just_too_big_room_size = y.bigger_room_size
ORDER BY y.class_nbr

-- Obviously there is contention for the room r4 but that is a different problem.

Post #852933
Posted Monday, January 25, 2010 8:36 AM
SSC Rookie

SSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC Rookie

Group: General Forum Members
Last Login: Thursday, February 02, 2012 7:24 AM
Points: 30, Visits: 109
This solution uses the logic that has been used in the past to accomplish pseudo line numbers from unique keys. The reason I have two code blocks is to show that it could be done without the additional sub-select. I think the additional one is more readable, but for the sake of elegance or being clever without obscure I figured I could show it both ways. It is the same exact logic. The idea is creating a count of records that are less than or equal or simply less than to get a count starting at zero. In this case I used less than or equal to match the logic and used whichever one mated to the class_nbr to see the 'first' or lowest room_size. I was able to simply put this into the where clause for the first example, but if that was too obscure syntax, in the second one I simply created a sub-query.

This will definitely work as far back as SQL Server 2000.

select c.class_nbr
, c.class_size
, r.room_nbr
, r.room_size
from classes c
join rooms r
on c.class_size <= r.room_size
where (select count(*)
from classes cc
join rooms rr
on cc.class_size <= rr.room_size
where cc.class_nbr = c.class_nbr
and rr.room_size <= r.room_size
) = 1
order
by c.class_nbr

select a.class_nbr
, a.class_size
, a.room_nbr
, a.room_size
from (
select c.class_nbr
, c.class_size
, r.room_nbr
, r.room_size
, (select count(*)
from classes cc
join rooms rr
on cc.class_size <= rr.room_size
where cc.class_nbr = c.class_nbr
and rr.room_size <= r.room_size
) qual
from classes c
join rooms r
on c.class_size <= r.room_size
) a
where a.qual = 1
order
by a.class_nbr

Post #853048
Posted Monday, January 25, 2010 12:12 PM
Old Hand

Old HandOld HandOld HandOld HandOld HandOld HandOld HandOld Hand

Group: General Forum Members
Last Login: Yesterday @ 9:27 AM
Points: 314, Visits: 1,452
Since I used to work in college administration for ten years, some of which was spent doing course-room assignments at NYU, this problem is all too familiar. Since space is the the most valued commodity in New York City, there's no way I'd let a classroom be partially filled -- max out the space whenever possible.

Consequently, for this challenge, I've taken the liberty to make the joins as less-than-or-equal / greater-than-or-equal.

I don't know if my proposed solution is breaking any of Celko's rules, but it seems to me that a correlated query that looks for the max class size that is less-than-or-equal to the room size provides a solution that would work for me in the real world:
SELECT
A.[ROOM_NBR]
,A.[ROOM_SIZE]
,B.[CLASS_NBR]
,B.[CLASS_SIZE]
FROM
#ROOMS A
JOIN #CLASSES B
ON A.[ROOM_SIZE] >= B.[CLASS_SIZE]
WHERE
B.[CLASS_SIZE] = ( SELECT
MAX(C.[CLASS_SIZE])
FROM
#CLASSES C
WHERE
C.[CLASS_SIZE] <= A.[ROOM_SIZE] )
ORDER BY
A.[ROOM_SIZE] DESC
,B.[CLASS_SIZE] DESC

Here are the results:
ROOM_NBR ROOM_SIZE   CLASS_NBR CLASS_SIZE
-------- ----------- --------- -----------
r4 85 c1 80
r1 70 c2 70
r6 65 c3 65
r7 55 c4 55
r3 50 c5 50
r2 40 c6 40


Don't know exactly how portable the query is to other systems (given the sub query and the use of an embedded aggregate function).

Nonetheless, the solution presents itself satifactorily, I believe.

--Pete




Post #853219
Posted Tuesday, January 26, 2010 4:02 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
WITH Matches AS (
SELECT
class_nbr,
class_size,
room_nbr,
room_size,
exact_match = CASE WHEN class_size = room_size THEN 1 ELSE 0 END
FROM Classes, Rooms
WHERE class_size <= room_size
),
Preferences AS (
SELECT
class_nbr,
class_size,
class_room_pref = ROW_NUMBER() OVER (PARTITION BY class_nbr ORDER BY exact_match, room_size, room_nbr),
room_nbr,
room_size,
room_class_pref = ROW_NUMBER() OVER (PARTITION BY room_nbr ORDER BY exact_match, class_size DESC, class_nbr)
FROM Matches m
WHERE NOT EXISTS (
SELECT 1
FROM Matches
WHERE room_nbr = m.room_nbr
AND class_size > m.class_size
)
),
Final AS (
SELECT
class_nbr,
class_size,
room_nbr,
room_size,
final_pref = ROW_NUMBER() OVER (PARTITION BY class_nbr ORDER BY class_room_pref)
FROM Preferences p
WHERE NOT EXISTS (
SELECT 1
FROM Preferences
WHERE room_nbr = p.room_nbr
AND class_room_pref = room_class_pref
AND room_class_pref < p.room_class_pref
)
)
SELECT
c.class_nbr,
c.class_size,
f.room_nbr,
f.room_size
FROM Classes c
LEFT JOIN Final f ON c.class_nbr = f.class_nbr AND f.final_pref = 1
ORDER BY 1

This code will allocate the smallest room that is large enough to accommodate each class with room for expansion or, if no such room exists, it allocates an exact size match (if available). It also takes room contention in to account (ie, it only allocates 1 class per room and 1 room per class)

EDIT: It will also deal with multiple classes/rooms of the same size
Post #853497
Posted Tuesday, January 26, 2010 10:59 AM
Forum Newbie

Forum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum Newbie

Group: General Forum Members
Last Login: Wednesday, February 20, 2013 9:44 AM
Points: 1, Visits: 41
The following code will accomplish the task. To switch the T-join from ascending to ascending we just need to comment/ uncomment the Min or Max lines.

I will describe the process, reading from innermost parentheses to outmost query.

-Create a cartesian product of the classes and rooms tables using the given condition class_size< room_size
-Find the minimum room size for each class size
For Ascending
-Find the minimum class_size for the resulting minimum of the room size
For Descending
-Find the maximum class_size for the resulting minimum of the room size
-Join back to the original table to get the room and class numbers


select classes.*,rooms.*
from (
Select min_rm
,min(class_size) as cls -- Ascending
-- ,max(class_size) as cls -- Descending
from(
select class_nbr,class_size
,min(room_size) as min_rm
from (
select class_nbr,class_size,room_nbr,room_size
from classes,rooms
where (class_size < room_size)
) as CartesianProduct
group by class_nbr,class_size
) as PossibleRoomFits
group by min_rm
) as Result
inner join classes
on class_size=cls
inner join rooms
on room_size=min_rm
order by class_nbr

Post #853829
Posted Tuesday, January 26, 2010 3:08 PM


SSCrazy

SSCrazySSCrazySSCrazySSCrazySSCrazySSCrazySSCrazySSCrazy

Group: General Forum Members
Last Login: Monday, April 14, 2014 3:07 PM
Points: 2,382, Visits: 3,369
Liam, it's a clever way to accomplish the task.
Add Room 9 with 90 seats to the sample data and run your solution again.



N 56°04'39.16"
E 12°55'05.25"
Post #854002
Posted Tuesday, January 26, 2010 3:12 PM


SSCrazy

SSCrazySSCrazySSCrazySSCrazySSCrazySSCrazySSCrazySSCrazy

Group: General Forum Members
Last Login: Monday, April 14, 2014 3:07 PM
Points: 2,382, Visits: 3,369
Absinthe, it's a clever solution but fails for the same reason as Liam's.
Add a new class c9 with 64 students and run your suggestion again.



N 56°04'39.16"
E 12°55'05.25"
Post #854006
Posted Tuesday, January 26, 2010 3:14 PM


SSCrazy

SSCrazySSCrazySSCrazySSCrazySSCrazySSCrazySSCrazySSCrazy

Group: General Forum Members
Last Login: Monday, April 14, 2014 3:07 PM
Points: 2,382, Visits: 3,369
PeterZeke, it's a fast solution but fails for the same reason as Liam's.
Add a new room r9 with 90 seats and run your query again.



N 56°04'39.16"
E 12°55'05.25"
Post #854007
Posted Tuesday, January 26, 2010 3:22 PM


SSCrazy

SSCrazySSCrazySSCrazySSCrazySSCrazySSCrazySSCrazySSCrazy

Group: General Forum Members
Last Login: Monday, April 14, 2014 3:07 PM
Points: 2,382, Visits: 3,369
Pierre, this is the first solution I see with ROW_NUMBER. But you have to beware of the limitations you build in you logic.
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 #854009
« Prev Topic | Next Topic »

Add to briefcase 12345»»»

Permissions Expand / Collapse