Ben Nadel
On User Experience (UX) Design, JavaScript, ColdFusion, Node.js, Life, and Love.
I am the chief technical officer at InVision App, Inc - a prototyping and collaboration platform for designers, built by designers. I also rock out in JavaScript and ColdFusion 24x7.
Meanwhile on Twitter
Loading latest tweet...
Ben Nadel at RIA Unleashed (Nov. 2010) with: Carol Loffelmann

Finding And Plotting Room Requirements For Concurrent Event Sessions

By Ben Nadel on
Tags: ColdFusion

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.


 
 
 

 
UXMovies.com takes Google Movie showtimes and plots them on a gantt-chart-like visual in order to present movies show times in a visual manner.  
 
 
 

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:


 
 
 

 
 Event sessions displayed on a room-based gantt chart. 
 
 
 

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).



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.)

Reply to this Comment

@Rick,

I know nothing about World of Warcraft... but that looks awesome! Maybe I'm just a sucker for charts :)

Reply to this Comment

@Ben, you forgot to allow for the time to clean up popcorn, spilled soda, and scrape bubblegum off the seats :-)

Reply to this Comment

@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.

Reply to this Comment

Post A Comment

You — Get Out Of My Dreams, Get Into My Comments
Live in the Now
Oops!
Comment Etiquette: Please do not post spam. Please keep the comments on-topic. Please do not post unrelated questions or large chunks of code. And, above all, please be nice to each other - we're trying to have a good conversation here.