Booking Availability Algorithm

Question

I've been tasked with creating a booking system and need to figure out when rooms are available at specific time slots on each day.

There are 5 available meeting rooms that can be booked at fixed times each day, these times slots are:

• 07:00 for 13 hours
• 13:00 for 24 hours
• 13:00 for 48 hours

What is the best way to calculate available slots (and fully booked days) for any visitors looking to book these rooms?

I've seen the Minimum Number of Platforms algorithm which looks along the right lines but I can't think how to apply this to checking specific dates/time slots. I also feel this could be a very resource intense calculation if I was having to calculate the availability for the next 365 days.

Any help would be greatly appreciated.

Answer 1

With thanks to MZB, I managed to solve this by doing the following:

1. Retrieve all existing future bookings
2. Loop through the available booking slots, in my question there were 3:

• 07:00 for 13 hours
• 13:00 for 24 hours
• 13:00 for 48 hours

3. For each booking slot, loop through the booked tickets and check whether the current booking slot overlaps any of them.
4. If the number of overlaps for this booking slot is greater than or equal to the maximum number of rooms, this booking slot is not available for hire.

Here is some pseudocode that outlines the process:

foreach ($booking_slots as $booking_slot) {
    foreach ($booked_tickets as $booked_ticket) {

        // Add a check here to make sure we are not processing similar
        // bookings unneccesarily.

        // Create a DateTime object to hold the booked start date
        $booked_start = new DateTime($booked_ticket->start_date);

        // Create a DateTime object using the date of the booked ticket but
        // the time of the booking slot.
        $slot_start = $booked_start->setTime($booking_slot->start_time);

        // Check whether the created booking slot starts after our existing
        // booking, if so modify $slot_start so it is X days before $booked_start
        if ($slot_start > $booked_start && $booking_slot->duration >= HOURS_IN_DAY) {
            $days_previous = ceil($booking_slot->duration / HOURS_IN_DAY);
            $slot_start = $slot_start->modify("-$day_previous days");
        }

        // With our final $slot_start, create $slot_end based on the
        // $booking_slot duration.
        $slot_end = $slot_start->modify("+$booking_slot->duration hours")


        $overlap = 0;
        foreach ($booked_tickets as $ticket) {
            if (check_for_overlap()) {
                 $overlap++;
            }
        }

        if ($overlap >= MAXIMUM_ROOMS) {
            // Flag as unavailable
        }
    }
}

The check_for_overlap() function would look something like follows:

// Where $a & $b are objects containing start/end dates to compare
function check_for_overlap($a, $b) {
    return ($a->start_date > $b->start_date && $a->start_date < $b->end_date)
            || ($a->end_date > $b->start_date && $a->end_date < $b->end_date)
            || ($b->start_date >= $a->start_date && $b->start_date < $a->end_date);
}

This seems to work really well from my tests but would be open to feedback on areas of improvements or if it is falling short anywhere.

Answer 2

I feel you've missed something important out of the problem formulation.

A key observation here is that if the maximum booking length is 48 hours, then you only need to look at the previous two days to determine if a meeting room is free or empty.

So (assuming a real problem and thus a database backed solution) pulling all the bookings for each room for the current day and the previous two days out of the database will allow you to determine availability on a given day.

Finding the next available slot is a sequential pass through the database from the current date keeping track of which rooms are available - ditto for determining fully booked days.

The Minimum Number of Platforms problem seems to be a red herring here: you aren't looking for how many meeting rooms to build.