Find common timeslots for consecutive days

Question

Imagine you want to reserve a classroom over several days. You get a schedule, from the school, telling you when a certain classroom is still free. To make it easy for your students, you want to reserve the classroom at the same time every day. Regrettably the schedule is long and complex, and you cannot figure out when the classroom will be free on all the days you need it.

The code below tries to solve that problem. It finds free time slots that are common to all dates, and their given free time slots.

It divides the day in 96 quarters of an hour (4 x 24), and creates an array for them. This is called a 'timeline'. Then the time slots, for each date, are matched against a blank timeline, creating a timeline for those dates. The special trick is combining these timelines in timeline_intersect(), effectively doing an AND operation on all array values. Finally it turns the timeline back into time slots.

This code does return the expected result.

<?php

// input data
$openTimeslots = ['02-09-2021' => [ '8:00-10:00', '16:00-19:00'],
                  '03-09-2021' => [ '7:00-10:00', '16:15-19:00', 
                                   '14:00-16:00', '13:00-14:15'],
                  '04-09-2021' => [ '7:15-10:00', '15:15-18:15']];

const QUARTER_FREE = 'free'; // unused
const QUARTER_USED = 'used'; // this quarter falls within a time slot

function newTimeline($status = QUARTER_FREE)
{
    $timeline = [];
    for ($quarter = 0; $quarter < 4 * 24; $quarter++) {
      $timeline[$quarter] = $status;
    }
    return $timeline;
}

function toTime($quarter)
{
    return sprintf('%02d', intdiv($quarter, 4)) . ':' . 
           sprintf('%02d', (($quarter % 4) * 15));
}

function toQuarters($time)
{
    list($hours, $minutes) = explode(':', $time);
    return (4 * $hours) + intdiv($minutes, 15);
}

function fillTimelineWithTimeslot($timeline, $timeslot)                  
{
    list($startTime, $finishTime) = explode('-', $timeslot);
    for ($quarter = toQuarters($startTime); $quarter < toQuarters($finishTime); $quarter++) {
        $timeline[$quarter] = QUARTER_USED;
    }
    return $timeline;
}

function extractTimeslotsFromTimeline($timeline)                  
{
    $timeslots = [];
    $inUse = FALSE;
    foreach ($timeline as $quarter => $usage) {
        if ($inUse && ($usage == QUARTER_FREE)) {
            $timeslots[] = toTime($startQuarter) . '-' . toTime($quarter);
            $inUse = FALSE;
        }
        elseif (!$inUse && ($usage == QUARTER_USED)) {
            $startQuarter = $quarter;
            $inUse = TRUE;
        }
    }
    return $timeslots;
}
                  
function timeline_intersect($timeline1, $timeline2)
{
    foreach ($timeline2 as $quarter => $usage) {
        $bothUsed = ($timeline1[$quarter] == QUARTER_USED) && 
                    ($usage == QUARTER_USED);
        $timeline1[$quarter] = $bothUsed ? QUARTER_USED : QUARTER_FREE;
    }
    return $timeline1;
}

// start of algorithm

$combinedTimeline = newTimeline(QUARTER_USED);

foreach ($openTimeslots as $date => $timeslots) {
    $timeline = newTimeline();
    foreach ($timeslots as $timeslot) {
        $timeline = fillTimelineWithTimeslot($timeline, $timeslot);
    }    

    $combinedTimeline = timeline_intersect($combinedTimeline , $timeline);    
}

var_export(extractTimeslotsFromTimeline($combinedTimeline));

Here is a PHP fiddle. The result is:

array (
  0 => '08:00-10:00',
  1 => '16:15-18:15'
)

If required this code could easily be converted to work with minutes, instead of quarters of hours, but since the time slots are given in quarters of hours this is, I think, the most efficient way to do this.

The requirements are:

• Time slot are set in whole quarters of hours. Only valid slots are given.
• Should be able to work with many dates.
• Should be able to work with many time slots.

My questions are:

• Is there a more efficient, more optimized, way to do this?
• Did I miss any bugs? (I hope not!)
• I used simple functions. Would OOP do a better job? If so, why? And how?

Have some fun playing with this code, and thank you for reading this.

Answer 1

General comments

This code looks well-written and after playing with it a few times I feel I grok it. Initially it seemed counter-intuitive to use the constant for free to denote timeslots that were NOT open but the comments next to the constants make it clearer.

The algorithm

I haven't been able to come up with any simpler algorithm for determining the intersection of time slots. I did consider that instead of using strings a simple 0 or 1 could be used to denote whether a timeslot was used or not. This would allow minimizing memory usage and also allow simplification of the function to compute the intersection - e.g. it could use bitwise operators instead of strict equality.

Other simplifications

new timeline array

Function newTimeline() can be simplified to just a call to array_fill():

return array_fill(0, 4 * 24, $status);

Destructuring arrays

As of PHP 7.1 array assignment can be used to destructure arrays¹. Instead of using list() when exploding strings like timeslots and times into two parts, a simple array can be used. This may not save much processing time since list() is just a language construct² but it is simpler to type.

e..g. in toQuarters():

list($hours, $minutes) = explode(':', $time);

can be simplified to

[$hours, $minutes] = explode(':', $time);

and in fillTimelineWithTimeslot():

list($startTime, $finishTime) = explode('-', $timeslot);

can be simplified to:

[$startTime, $finishTime] = explode('-', $timeslot);

long for loop declaration

In fillTimelineWithTimeslot() the line with the for loop is a bit long.

for ($quarter = toQuarters($startTime); $quarter < toQuarters($finishTime); $quarter++) {

It could be changed to a foreach() using the range() function:

foreach(range(toQuarters($startTime), toQuarters($finishTime) - 1) as $quarter) {

Though if you are really trying to optimize for performance calling range() might not be wise - in that case the call toQuarters($finishTime) in the while condition of the for loop could be moved out to a variable instead of being called on each iteration.

Answer 2

I suppose your code strikes me as doing too much work and using too much memory.

The truth is that your well-formatted timeslot start and end substrings are perfectly suited for simple greater than and less than evaluations.

Trimming down the "master array" as you iterate only improves performance rather than creating 96-element arrays with togglable values.

I would completely rewrite this way...

Code: (Demo)

$openTimeslots = ['02-09-2021' => [ '8:00-10:00', '16:00-19:00'],
                  '03-09-2021' => [ '7:00-10:00', '16:15-19:00', 
                                   '14:00-16:00', '13:00-14:15'],
                  '04-09-2021' => [ '7:15-10:00', '15:15-18:15']];

$common = array_map(
    fn($timeRange) => explode('-', $timeRange),
    array_shift($openTimeslots)
);

foreach ($openTimeslots as $slots) {
    foreach ($slots as $slot) {
        [$start, $end] = explode('-', $slot);
        foreach ($common as [&$commonStart, &$commonEnd]) {
            if ($start >= $commonStart && $start < $commonEnd) {
                $commonStart = $start;
            }
            if ($end > $commonStart && $end <= $commonEnd) {
                $commonEnd = $end;
            }
        }
    }
}
var_export(
    array_map(
        fn($subarray) => implode('-', $subarray),
        $common
    )
);

Answer 3

I've given it another try myself. I still think the idea of using timelines is not a bad one, but as mickmackusa rightfully stated: "it is doing too much work and using too much memory", because I store a full timeline in memory.

My new approach is still using timelines, but much simpler ones. For instance:

['8:00-10:00', '16:00-19:00']

will be transformed into this timeline:

[800 => 1000, 1600 => 1900]

Basically an array in which the keys are the start of a time slot and the value is the finish of a time slot. I use integers. The only reason I do this transformation is to make it easier to compare time slots.

The trick is again in intersecting two timelines. I compare all time slots in those two timelines to each other. Any overlap is stored in the new timeline that will be returned.

Here's the code:

$openTimeslots = ['02-09-2021' => [ '8:00-10:00', '16:00-19:00'],
                  '03-09-2021' => [ '7:00-10:00', '16:15-19:00',
                                   '14:00-16:00', '13:00-14:15'],
                  '04-09-2021' => [ '7:15-10:00', '15:15-18:15',
                                   '18:30-18:45']];

function timeslotsToTimeline($timeslots)
{
    $timeline = [];
    foreach ($timeslots as $timeslot) {
        $intTimes = sscanf(str_replace(':', '', $timeslot), "%d-%d");
        $timeline[$intTimes[0]] = $intTimes[1];
    }
    return $timeline;
}

function timelineToTimeslots($timeline)
{
    $timeslots = [];
    foreach ($timeline as $start => $finish) {
        $timeslots[] = intdiv($start, 100) . ':' . substr($start, -2) . '-' .
                       intdiv($finish, 100) . ':' . substr($finish, -2);
    }                   
    return $timeslots;
}

function intersectTimelines($timeline1, $timeline2)
{
    $newTimeline = [];
    foreach ($timeline1 as $start1 => $finish1) {
        foreach ($timeline2 as $start2 => $finish2) {
            $newStart = max($start1, $start2);
            $newFinish = min($finish1, $finish2);
            if ($newStart < $newFinish) {
               $newTimeline[$newStart] = $newFinish;
            }
        }
    }
    return $newTimeline;
}

$commonTimeline = timeslotsToTimeline(array_shift($openTimeslots));

foreach ($openTimeslots as $timeslots) {
    $newTimeline = timeslotsToTimeline($timeslots);
    $commonTimeline = intersectTimelines($commonTimeline, $newTimeline);
}

$commonTimeslots = timelineToTimeslots($commonTimeline);

var_export($commonTimeslots);

This code returns:

array (
  0 => '8:00-10:00',
  1 => '16:15-18:15',
  2 => '18:30-18:45',
)

See a demo of the code

I think it should be possible to do away with the whole transformation to timelines, but I think the code would be harder to read if I did that. OK, I tried it, and it works, but what do you think?

<?php

$openTimeslots = ['02-09-2021' => [ '8:00-10:00', '16:00-19:00'],
                  '03-09-2021' => [ '7:00-10:00', '16:15-19:00',
                                   '14:00-16:00', '13:00-14:15'],
                  '04-09-2021' => [ '7:15-10:00', '15:15-18:15',
                                   '18:30-18:45']];

function intersectTimeslots($timeslots1, $timeslots2)
{
    $newTimeslots = [];
    foreach ($timeslots1 as $timeslot1) {
        [$start1, $finish1] = sscanf(str_replace(':', '', $timeslot1), "%d-%d");
        foreach ($timeslots2 as $timeslot2) {
            [$start2, $finish2] = sscanf(str_replace(':', '', $timeslot2), "%d-%d");
            $newStart = max($start1, $start2);
            $newFinish = min($finish1, $finish2);
            if ($newStart < $newFinish) {
               $newTimeslots[] = substr_replace($newStart, ':', -2, 0) . '-' . 
                                 substr_replace($newFinish, ':', -2, 0);
            }
        }
    }
    return $newTimeslots;
}

$commonTimeslots = array_shift($openTimeslots);

foreach ($openTimeslots as $timeslots) {
   $commonTimeslots = intersectTimeslots($commonTimeslots, $timeslots);
}

var_export($commonTimeslots);

See the demo code of this.