Finding And Plotting Room Requirements For Concurrent Event Sessions
A while back, I made a small website called www.UXMovies.com. The idea of the site was simple - you put in a Google Movies page and UXMovies.com will plot the movies on a sort-of Gantt chart for a visual understanding of when movies start and end in relationship to each other. The complicated thing about this task was that I only had the showtimes of each movie - I didn't know how many theaters were being used for screening. As such, I had to calculate the number of theaters for each movie based on the maximum number of concurrent screenings. This ended up being a fun little algorithm that I thought I would share.
When it comes to a movie theater, we're actually working with two different variables - the number of movies being shown and the number of screens showing each movie. This makes the movie theater problem slightly more complex; however, since the list of titles is locked down, you can divide and conquer this problem for each title. Meaning, don't worry about concurrent movies - just think about concurrent screenings for a given movie.
Rather than worry about movies, however, let's look at this problem in a simple, abstract way. Imagine that all we have is a single database table with some Start and End times for the sessions at a given event:
- id
- startTime
- endTime
When thinking about concurrent sessions, there are three ways in which two session can overlap. One session can start in the middle of another session; one session can end in the middle of another session; or, one session can start before and then after another session - straddling it entirely. If any of these is true, the event will require 2 rooms to hold the overlapping sessions.
And, of course, sessions are never back-to-back; there is typically a 10 or 15 minute window allotted at the end of an event to allow attendees time to leave the room, take a bathroom break, and enter the next room. This "buffer" time can be thought of as being appended to the end of each session. So, if we want a 15-minute inter-session break, we can simply add 15 minutes to the duration of each session when booking the rooms back-to-back.
Ok, enough talk, let's take a look at the code. In the following demo, we're going to populate the event table with random session data; then, we're going to plot that data across the minimum number of rooms required.
<!---
First, we need to build up the list of events that are being held
at this particular location. For this demo, we'll randomly build
events within the course of the day.
--->
<cfquery name="insertEvents" datasource="testing">
<!--- Clear out the testing table. --->
TRUNCATE TABLE event;
<!---
Create randomly timed events to all be held in the same day.
We will have to determine (afterward) how many rooms it will
take to hold an event of such size.
--->
<cfloop
index="eventIndex"
from="1"
to="15"
step="1">
<!--- Create a random start time between 8AM and 5PM. --->
<cfset startTime = (
createDateTime( 2011, 8, 29, 8, 0, 0 ) +
createTimeSpan( 0, 0, randRange( 0, 540 ), 0 )
) />
<!---
Create a random end time for the event between 45 mins
and 2 hours.
--->
<cfset endTime = (
startTime +
createTimeSpan( 0, 0, randRange( 45, 120 ), 0 )
) />
<!--- Insert the randomly timed event. --->
INSERT INTO event
(
startTime,
endTime
) VALUES (
<cfqueryparam value="#startTime#" cfsqltype="cf_sql_timestamp" />,
<cfqueryparam value="#endTime#" cfsqltype="cf_sql_timestamp" />
);
</cfloop>
</cfquery>
<!--- ----------------------------------------------------- --->
<!--- ----------------------------------------------------- --->
<!--- ----------------------------------------------------- --->
<!--- ----------------------------------------------------- --->
<!---
Now, let's determine which room each event should be held in.
For this part of the demo, we will simply give each room an
incrementing ID to keep track of it. Let's query for the events
with a zerod-out room ID.
NOTE: We are going to build some buffer time into a calculated
date/time column. This will give people an opporotunity to get
out of the current room and into the next. By building this
concept directly into the query, it will make the future query
(of queries) much easier.
--->
<cfquery name="events" datasource="testing">
<!--- Get a reference to the buffer time. --->
SET @buffer = <cfqueryparam value="15" cfsqltype="cf_sql_integer" />;
<!--- Query for events. --->
SELECT
e.id,
e.startTime,
e.endTime,
<!---
Calculate the buffered start time and end time. This will
simply make our query-of-queries a LOT easier to perform.
--->
(e.endTime + INTERVAL @buffer MINUTE) AS bufferedEndTime,
<!--- This will be populated shortly. --->
( 0 ) AS roomID
FROM
event e
ORDER BY
e.startTime ASC
;
</cfquery>
<!--- Find each session room. --->
<cfloop query="events">
<!---
For this session, gather all of the overlapping sessions
that have already been assigned to a room. If a session
does not yet have a room assignment, then it can't possibly
be used in this part of the calculation (as it is not
causing a conflict).
--->
<cfquery name="concurrencies" dbtype="query">
SELECT
id,
roomID
FROM
events
WHERE
<!--- Do not include THIS session in calculation. --->
id != <cfqueryparam value="#events.id#" cfsqltype="cf_sql_integer" />
AND
<!---
Only get overlapping sessions that have been assigned
to a room (as we only care about events that compete
for rooms.
--->
roomID != <cfqueryparam value="0" cfsqltype="cf_sql_integer" />
AND
<!---
Now, check for sessions that overlap with this one,
based on the start and end (buffered) time.
--->
(
<!--- Check start time. --->
startTime BETWEEN
<cfqueryparam value="#events.startTime#" cfsqltype="cf_sql_timestamp" />
AND
<cfqueryparam value="#events.bufferedEndTime#" cfsqltype="cf_sql_timestamp" />
OR
<!--- Check end time. --->
bufferedEndTime BETWEEN
<cfqueryparam value="#events.startTime#" cfsqltype="cf_sql_timestamp" />
AND
<cfqueryparam value="#events.bufferedEndTime#" cfsqltype="cf_sql_timestamp" />
OR
<!--- Check straddling time. --->
(
startTime < <cfqueryparam value="#events.startTime#" cfsqltype="cf_sql_timestamp" />
AND
bufferedEndTime > <cfqueryparam value="#events.bufferedEndTime#" cfsqltype="cf_sql_timestamp" />
)
)
ORDER BY
roomID ASC
</cfquery>
<!---
Get the list of occupied room IDs from the concurrent
session. We know we can't use any of these for our current
event in question.
--->
<cfset busyRoomIDs = valueList( concurrencies.roomID ) />
<!---
Now that we've found all the concurrent sessions being held
against this one, we have to find the first available room.
We know we can't have more than N+1 rooms.
--->
<cfloop
index="freeRoomID"
from="1"
to="#(concurrencies.recordCount + 1)#"
step="1">
<!---
Check to see if this room is free (ie. not being used by
any of the concurrent session).
--->
<cfif !listFind( busyRoomIDs, freeRoomID )>
<!---
This room is not taken - assign it to the current
session so that no other session can take it in
this time slot.
NOTE: Assignment done below.
--->
<cfbreak />
</cfif>
</cfloop>
<!--- Assign the free room ID. --->
<cfset events[ "roomID" ][ events.currentRow ] = javaCast( "int", freeRoomID ) />
</cfloop>
<!--- ----------------------------------------------------- --->
<!--- ----------------------------------------------------- --->
<!--- Reset the output buffer. --->
<cfcontent type="text/html" />
<cfoutput>
<!DOCTYPE html>
<html>
<head>
<title>Finding Room Requirements For Concurrent Events</title>
<style type="text/css">
div.room {
border: 1px solid black ;
height: 30px ;
position: relative ;
}
div.session {
background-color: black ;
border-right: 15px solid red ;
color: white ;
left: 0px ;
line-height: 30px ;
position: absolute ;
text-indent: 10px ;
top: 0px ;
}
</style>
</head>
<body>
<h1>
Finding Room Requirements For Concurrent Events
</h1>
<!---
Now, we want to plot all of the event sessions. In order
to do that, we'll use an offset that starts relative to
the beginning of the day.
--->
<cfset dayStart = createDateTime( 2011, 8, 29, 8, 0, 0 ) />
<!--- Output all the rooms and the related sessions. --->
<cfloop
index="roomID"
from="1"
to="#arrayMax( events[ 'roomID' ] )#"
step="1">
<!--- Query for the events in this room. --->
<cfquery name="sessions" dbtype="query">
SELECT
id,
startTime,
endTime
FROM
events
WHERE
roomID = <cfqueryparam value="#roomID#" cfsqltype="cf_sql_integer" />
ORDER BY
startTime ASC
</cfquery>
<h3>
Room #roomID#
</h3>
<div class="room">
<!--- Output each session in this room. --->
<cfloop query="sessions">
<!---
Determine the left offset - the TIME at which
the event will start. For our purposes, we'll
go 1px / minute.
--->
<cfset leftOffset = dateDiff("n", dayStart, sessions.startTime ) />
<!---
Determine the width of the session - the
DURATION it will run for. For our purposes, we'll
go 1px / minute.
--->
<cfset width = dateDiff( "n", sessions.startTime, sessions.endTime ) />
<div
class="session"
style="left: #leftOffset#px ; width: #width#px ;">
[ #sessions.id# ]
</div>
</cfloop>
</div>
</cfloop>
</body>
</html>
</cfoutput>
This approach uses a brute force method; we start with the earliest session and then keep adding sessions to rooms as they become available. I wish I knew a way to do this in a single query, but the complexity of it would probably stretch my mental capabilities beyond their limit. The good news is, the brute force approach is rather simple and very effective; all we do, really, is look at each session and then find all the sessions that are running in parallel.
When we run the above code, we get a page that looks like this:
As you can see, I used a red border to illustrate the 15-minute buffer available at the end of each event session. And, as you can see, we've pretty much used the minimum number of rooms possible.
Using the brute-force approach gives us the most accurate results. But, if you want a very rough estimate, you can use a single query. The problem with the single query approach is that it doesn't take into account the more advanced grouping of event sessions. So for example, if you look at the above screen shot, you'll see that events 10, 15, and 14 (top left) only take up 2 rooms. In a single query, it's much harder to take this kind of grouping into account; as such, the following code would determine that 3 rooms are necessary since session 15 overlaps with 2 other sessions.
<!---
Get a list of the concurrent times. In order to do that, we are
going to join the event table BACK to itself, and join each event
to the collection of concurrent events.
NOTE: When getting the concurrent sessions, we are going to build
in a 15-minute buffer for each session so that the people may
have time to exit one room and then enter another.
Also not that this is just an ****ESTIMATE**** of the required
rooms. This simple join does NOT take into account more advanced
overlapping solutions.
--->
<cfquery name="concurrencies" datasource="testing">
<!--- Get a reference to the buffer time. --->
SET @buffer = <cfqueryparam value="15" cfsqltype="cf_sql_integer" />;
<!--- Query the events that have concurrencies. --->
SELECT
e.id,
e.startTime,
e.endTime,
<!---
Get the number of concurrent events to this particular
event. We can find the highest value of this afterward.
--->
COUNT( * ) AS concurrentCount
FROM
event e
INNER JOIN
event c
ON
(
<!---
Don't join the event back to itself - we only
want to join it to concurrent events.
--->
e.id != c.id
AND
<!---
Check for concurrent events based on overlapping
times (including the buffered end time).
--->
(
<!--- Check start time. --->
c.startTime BETWEEN
e.startTime
AND
(e.endTime + INTERVAL @buffer MINUTE)
OR
<!--- Check end time. --->
(c.endTime + INTERVAL @buffer MINUTE) BETWEEN
e.startTime
AND
(e.endTime + INTERVAL @buffer MINUTE)
OR
<!--- Check straddling time. --->
(
c.startTime < e.startTime
AND
(c.endTime + INTERVAL @buffer MINUTE) > (e.endTime + INTERVAL @buffer MINUTE)
)
)
)
GROUP BY
e.id,
e.startTime,
e.endTime
ORDER BY
e.startTime ASC
;
</cfquery>
<!---
Get the highest number of concucrrent events. Since this query
was getting the concurrent event count, the number of rooms
needed will be the max value PLUS one (for the original event).
NOTE: If there were no concurrent sessions, we only need one
room for the events.
--->
<cfif concurrencies.recordCount>
<!--- Use the concurrent sessions to determine rooms space. --->
<cfset roomsRequired = (
arrayMax( concurrencies[ "concurrentCount" ] ) +
1
) />
<cfelse>
<!---
We only need one room since we have no overlapping sessions
in this event.
--->
<cfset roomsRequired = 1 />
</cfif>
<!--- Output the rooms required. --->
<cfoutput>
Rooms Required: #roomsRequired#
</cfoutput>
As you can see, we are getting our estimate by joining the event table back to itself. This algorithm uses the same basic time-based principles as the brute-force approach; it's just that this one doesn't take into account efficient overlapping. If we run this code on the same events table used in the previous demo, we get the following output:
Rooms Required: 8
As you can see, this very rough estimate allotted two more rooms than the 6 actually required when effective distribution was put in place. Honestly, I don't see any real use case for such an approximate value. I only put it here to try an cover all my bases.
Most of the time, when dealing with events, you start with a set number of rooms (or "tracks") and then try to populate them with sessions. In rare situations, such as with data APIs, however, you may need to reverse engineer the number of rooms based on the date/time of a particular event. Using a brute force approach, we can manually distribute overlapping session to determine minimum room requirements. Also, the same kind of approach could be used (with some modification) to plot overlapping events on a calendar (GMail style).
Want to use code from this post? Check out the license.
Reader Comments
Very nice. It's a surprisingly tricky problem, especially if you have a concern for space optimization.
I made something similar back when I was playing World of Warcraft:
http://rickosborne.org/wow/sp-gear/
(For a more interesting chart, use the Sources menu to Select All and then Apply Changes.)
@Rick,
I know nothing about World of Warcraft... but that looks awesome! Maybe I'm just a sucker for charts :)
@Ben, you forgot to allow for the time to clean up popcorn, spilled soda, and scrape bubblegum off the seats :-)
@Randall,
Unfortunately, that goes beyond my SQL skills :) You should see my apartment. Although, in all fairness, I did just buy a new vacuum, which I desperately needed.