Classroom scheduling

from the Artful Common Queries page


You have n student classes of known size, and m classrooms of known size, where m>=n. What's the best algorithm for assigning as many classes as possible to rooms of adequate size?

It's a version of the combinatorial knapsack problem. It's known to be NP-complete, which means it's possible to verify any correct solution but there is no known algorithm for quickly finding a correct solution. How then to proceed?

Early in 2010 Joe Celko resurrected the problem in a Simple Talk column, and challenged readers to improve on SQL Server solutions he'd published in the third edition of his "SQL for Smarties". Here's his small version of the problem in MySQL syntax:

DROP TABLE IF EXISTS Rooms, Classes;
CREATE TABLE Rooms(
  room_nbr CHAR(2) NOT NULL PRIMARY KEY, room_size INTEGER NOT NULL
) ENGINE=MyISAM;
CREATE TABLE Classes(
  class_nbr CHAR(2) NOT NULL PRIMARY KEY, class_size INTEGER NOT NULL
) ENGINE=MyISAM;
INSERT INTO Classes  
VALUES ('c1', 80),('c2', 70),('c3', 65),('c4', 55),('c5', 50),('c6', 40);
INSERT INTO Rooms 
VALUES ('r1', 70),('r2', 40),('r3', 50),('r4', 85),('r5', 30),('r6', 65),('r7', 55);

And here is the best solution posted by his contributors. It works in SQL Server since 2005, MySQL since version 8.0.2, and MariaDB since 10.2.6:

WITH 
  Matches AS (
    SELECT 
      class_nbr, class_size, room_nbr, room_size, 
      CASE WHEN class_size = room_size THEN 1 ELSE 0 END AS exact_match
    FROM Classes
    JOIN Rooms ON class_size <= room_size
  ),
  Preferences AS (
    SELECT
      class_nbr, class_size, 
      ROW_NUMBER() OVER (
        PARTITION BY class_nbr ORDER BY exact_match, room_size, room_nbr
      ) AS class_room_pref,
      room_nbr, room_size, 
      ROW_NUMBER() OVER (
        PARTITION BY room_nbr ORDER BY exact_match, class_size DESC, class_nbr
      ) AS room_class_pref
    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,
      ROW_NUMBER() OVER (PARTITION BY class_nbr ORDER BY class_room_pref)
      AS final_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;

In MySQL 8.0.2 it immediately yields this correct answer:

class_nbr class_size room_nbr room_size
   c1         80        r4       85
   c2         70        r1       70
   c3         65        r6       65
   c4         55        r7       55
   c5         50        r3       50
   c6         40        r2       40

Can we do the job without CTEs and analytic functions, i.e., if we're using MySQL before 8.0.2, or MariaDB before 10.2.6? Yes, but not nearly so elegantly.

ROW_NUMBER() numbers resultset rows based on row values. This entry shows two MySQL equivalents for it, one relying on user variables, the other on aggregation. For this problem we will use the user variable method.

CTEs provide an elegant syntax for building derived tables. The above CTE/Analytic query builds the derived table Matches, from which it builds the derived table Preferences, from which it builds the table Final, which it joins with Classes for the final result.

Here we'll lay out an unoptimised step-by-step. Basically, we build the Matches, Preferences and Final tables, one at a time, then copy the final step of the SQL Server query.

First the Matches table:

DROP TABLE IF EXISTS Matches;
CREATE TABLE Matches
  SELECT class_nbr, class_size, room_nbr, room_size, IF(class_size=room_size,1,0) AS exact_match 
  FROM Classes
  JOIN Rooms ON class_size <= room_size;

The Preferences table has two Row_Number() expressions to port, so we build each, then join them:

DROP TABLE IF EXISTS room_prefs;
SET @class_nbr_prev='', @ordPrev=0;
CREATE TABLE room_prefs
  SELECT ID, class_nbr, class_size, room_nbr, room_size, class_room_pref
  FROM (
    SELECT 
      ID, class_size, room_nbr, room_size,
      @ordPrev := IF( @class_nbr_prev=class_nbr, @ordPrev+1, 1 ) as class_room_pref, 
      @class_nbr_prev := class_nbr AS class_nbr
    FROM Matches m
    WHERE NOT EXISTS ( SELECT 1 FROM Matches WHERE room_nbr = m.room_nbr AND class_size > m.class_size )
    ORDER BY class_nbr, exact_match, room_size, room_nbr
  ) AS tmp ;

DROP TABLE IF EXISTS class_prefs;
SET @room_nbr_prev = '', @ordPrev=0;
CREATE TABLE class_prefs 
  SELECT ID, room_class_pref
  FROM (
    SELECT 
      ID, 
      @ordPrev := IF( @room_nbr_prev=room_nbr, @ordPrev+1, 1 ) as room_class_pref, 
      @room_nbr_prev := room_nbr AS room_nbr
    FROM Matches m
    WHERE NOT EXISTS ( SELECT 1 FROM Matches WHERE room_nbr = m.room_nbr AND class_size > m.class_size )
    ORDER BY room_nbr, exact_match, class_size DESC, class_nbr
  ) AS tmp ;

DROP TABLE IF EXISTS Preferences;
CREATE TABLE Preferences
  SELECT a.class_nbr, a.class_size, a.room_nbr, a.class_room_pref, a.room_size, b.room_class_pref 
  FROM room_prefs a
  JOIN class_prefs b USING(ID);

Now build the Final table from Preferences:

DROP TABLE IF EXISTS Final;
SET @class_nbr_prev = '', @ordPrev=0;
CREATE TABLE Final
  SELECT 
    room_nbr, room_size, class_size, 
    @ordPrev := IF( @class_nbr_prev=class_nbr, @ordPrev+1, 1 ) as final_pref, 
    @class_nbr_prev := class_nbr AS class_nbr
  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
  )
  ORDER BY class_nbr;

The final step is identical to the last step in the SQL Server version:

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; 
+-----------+------------+----------+-----------+
| class_nbr | class_size | room_nbr | room_size |
+-----------+------------+----------+-----------+
| c1        |         80 | r4       |        85 |
| c2        |         70 | r1       |        70 |
| c3        |         65 | r6       |        65 |
| c4        |         55 | r7       |        55 |
| c5        |         50 | r3       |        50 |
| c6        |         40 | r2       |        40 |
+-----------+------------+----------+-----------+

Looking for a juicy query optimisation problem?

Return to the Artful Common Queries page