Show available slots within time range taking into account already booked slots

Question

This script checks if a 60 min slot is available within a time range taking into account already booked slots. It works fine for the first already booked slot but does not take into account the second. Also if I change the first booked slot to 12:10 it will not detect it.

Basically, the idea is if there is a 60 min slot between the range and the already booked slots to show it.

For example,, if we have a range 9:00 to 15:00 and we have two booked slots from 11:10 and 14:00, to return available slots from 9:00, 10:00 and 12:10

$start_time = '2022-10-21 09:00:00';  //start time as string
$end_time = '2022-10-21 15:00:00';  //end time as string
$booked = ['2022-10-21 12:00:00','2022-10-21 13:00:00']; //booked slots as arrays
$start = DateTime::createFromFormat('Y-m-d H:i:s',$start_time); //create date time objects
$end = DateTime::createFromFormat('Y-m-d H:i:s',$end_time);  //create date time objects
$time1 = $start;
$count = 0;  //number of slots
$out = array();   //array of slots 
for($i = $start; $i<$end;)  //for loop 
{
    $avoid = false; 
    $t1 = date_timestamp_get($i);
    $t2 = $t1+(60*60);

    for($k=0;$k<sizeof($booked);$k+=2)  //if booked hour
    {
        $st = DateTime::createFromFormat('Y-m-d H:i:s',$booked[$k]);
        $en = DateTime::createFromFormat('Y-m-d H:i:s',$booked[$k+1]);
          
        if( $t1 >= date_timestamp_get($st) && $t2 <= date_timestamp_get($en)  )
        $avoid = true;   //yes. booked
    }
    $slots =[ $i->format('H:i'),$i->modify("+60 minutes")->format('H:i')];
    if(!$avoid && $i<$end)  //if not booked and less than end time
    {
        $count++;  
        array_push($out,$slots);  //add slot to array
    }
}
var_dump($out);   //array out

Here is link to sandbox https://onlinephp.io/c/b0b77

Additional information

Let's say that we have a free time frame from 10:00 until 13:00. What the script should return is 10:00, 11:00, and 12:00 as possibilities if the time slot is 60 min.

If the timeslot is 45 min. for example, it should return 10:00, 10:45, 11:30, and 12:15.

So, the possible variants should start from the first possible option increasing with the time slot (45, 60, or whatever time slot is set)

The slot cannot start from 10:12, 10:44, or another custom time

The Solutions

Both solutions below by Salman A and Jim are working as expected. Just use a little bit of a different approach.

Overlapping bookings - Update provided

If you have overlapping bookings as suggested by Salman A we have to first merge them and then send unique intervals only. I did it with that function

function mergeBookings($ranges)
{
    $retVal = [];
    //sort date ranges by begin time
    usort($ranges, function ($a, $b) {
        return strcmp($a['start'], $b['start']);
    });

    $currentRange = [];
    foreach ($ranges as $range) {
        // bypass invalid value
        if ($range['start'] >= $range['end']) {
            continue;
        }
        //fill in the first element
        if (empty($currentRange)) {
            $currentRange = $range;
            continue;
        }

        if ($currentRange['end'] < $range['start']) {
            $retVal[] = $currentRange;
            $currentRange = $range;
        } elseif ($currentRange['end'] < $range['end']) {
            $currentRange ['end'] = $range['end'];
        }
    }

    if ($currentRange) {
        $retVal[] = $currentRange;
    }

    return $retVal;
}

Then just use the function before sending the $booked array to the script. Like this

$booked = mergeBookings($booked);

Answer 1

This could be done with simple nested loops if booked dates are sorted. Notice the pattern in the data; end date from one row and start date from next row form an available range, in which you create the slots:

$start_time =                                        '2022-10-21 09:00:00';
$booked = array(
    array('start' => '2022-10-21 11:10:00', 'end' => '2022-10-21 12:10:00'),
    array('start' => '2022-10-21 14:00:00', 'end' => '2022-10-21 15:00:00')
);
$end_time =          '2022-10-21 15:00:00';
$slot_size = 60;
// data must be sorted by date
usort($booked, function($a, $b) {
    return DateTime::createFromFormat('Y-m-d H:i:s', $a['start']) <=> DateTime::createFromFormat('Y-m-d H:i:s', $b['start']);
});
$interval = new DateInterval('PT' . $slot_size . 'M');
$result = array();
for ($i = 0, $j = count($booked); $i <= $j; $i++) {
    // loop count + 1 times
    // first and last iterations are special
    $range_start = $i === 0 ? DateTime::createFromFormat('Y-m-d H:i:s', $start_time) : DateTime::createFromFormat('Y-m-d H:i:s', $booked[$i - 1]['end']);
    $range_end = $i < $j ? DateTime::createFromFormat('Y-m-d H:i:s', $booked[$i]['start']) : DateTime::createFromFormat('Y-m-d H:i:s', $end_time);
    $t1 = (clone $range_start);
    $t2 = (clone $range_start)->add($interval);
    while ($t2 <= $range_end) {
        $result[] = array('start' => $t1->format('Y-m-d H:i:s'), 'end' => $t2->format('Y-m-d H:i:s'));
        $t1->add($interval);
        $t2->add($interval);
    }
}
var_dump($result);

Answer 2

The algorithm you need to implement is as follows (I'm implementing it in pseudo-code for now):

booking_length <- 1h //1 hour, you can set this to something else
for dt <- start, dt <- end - booking_length, d <- d + booking_length
    b <- closest booking after d
    if (d + booking_length < b) then
        bookings.add(d)
    else
        d <- b + booking_length
    else
end for

The reason as of why I didn't implement this in PHP was that I did not have enough time to do so at the time of this writing. Let me know if this is not clear yet and whether you need PHP code.

Answer 3

You can use DatePeriod combined with DateInterval to create ranges or slots to which you can then check if the slot intersects with any of the booked slots:

/**
 * Create DatePeriod with start time & end times
 */
function createBookedDateTime(
    string $startDate,
    string $endDate
): DatePeriod {
    $start = new DateTime($startDate);
    $end = new DateTime($endDate);
    return new DatePeriod(
        $start,
        $start->diff($end),
        $end
    );
}

/**
 * Check if any of the booking values, previously added slot, or end of the
 * availability period intersect with the currently checked slot.
 */
function isAvailable(
    array $bookingArray,
    DateTime $dtToCheck,
    ?DatePeriod $prevSlot,
    DateInterval $bookingLength,
    DateTime $availabilityEnd
) {
    $isBooked = false;
    $intersectsPrevious = false;
    $dtPeriodToCheck = new DatePeriod(
        $dtToCheck,
        $bookingLength,
        (clone $dtToCheck)->add($bookingLength)
    );
    /** @var DatePeriod $bookedDt */
    foreach($bookingArray as $bookedDt) {
        if(
            (
                $dtPeriodToCheck->getStartDate() >= $bookedDt->getStartDate() &&
                $dtPeriodToCheck->getStartDate() < $bookedDt->getEndDate()
            ) ||
            (
                $dtPeriodToCheck->getEndDate() >= $bookedDt->getStartDate() &&
                $dtPeriodToCheck->getEndDate() < $bookedDt->getEndDate()
            )
        ) {
            $isBooked = true;
            break;
        }
    }
    if($prevSlot instanceof DatePeriod) {
        $intersectsPrevious =
            (
                $dtPeriodToCheck->getStartDate() >= $prevSlot->getStartDate() &&
                $dtPeriodToCheck->getStartDate() < $prevSlot->getEndDate()
            ) ||
            (
                $dtPeriodToCheck->getEndDate() >= $prevSlot->getStartDate() &&
                $dtPeriodToCheck->getEndDate() < $prevSlot->getEndDate()
            );
    }
    return $isBooked === false && $intersectsPrevious === false &&
        $dtPeriodToCheck->getEndDate() <= $availabilityEnd;
}

// Length of booking
$bookingLength = new DateInterval('PT1H');

// DatePeriod array of already booked slots
$booked = [
    createBookedDateTime('2022-10-21 11:10:00', '2022-10-21 12:15:00'),
    createBookedDateTime('2022-10-21 12:15:00', '2022-10-21 12:45:00'),
];

// The range of time available for booking divided into slots by
// the $bookingLength interval.
$availStart = new DateTime('2022-10-21 09:00:00');
$availEnd = new DateTime('2022-10-21 15:00:00');
$availability = new DatePeriod($availStart, new DateInterval('PT5M'), $availEnd);

// Array of available booking slots
$availableToBook = array();
$prevSlot = null;

// Loop to find available booking slots
/** @var DateTime $available */
foreach($availability as $available) {

    if(isAvailable($booked, $available, $prevSlot, $bookingLength, $availEnd)) {
        $availableToBook []= $prevSlot = new DatePeriod(
            $available,
            $bookingLength,
            (clone $available)->add($bookingLength)
        );
    }

}

var_dump($availableToBook);

Here I have created a function which creates a DatePeriod for each of the booked slots by using the start & end date & time.

The second function, isAvailable, is called within the loop to check if the time slot intersects with any of the booked entries, previously added slot, or the end of the availability period. If not, it is added to the $availableToBook array.

You can change the booking length by altering $bookingLength to whatever you want (it is set to one hour). You can change it to 15 minutes (PT15M), 30 minutes (PT30M), 45 minutes (PT45M), or whatever time length you want.