3
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ Why cannot I find in your code where specific slots are filled? I can see $openTimeslots at the top of the snippet, but where is the declaration of what is used? Why does the input have 3 days listed, but the output loses the date relationship? I think I am misunderstanding the purpose of your script. As an aside, please use 3v4l.org as your demo sandbox because sandbox.onlinephpfunctions.com is positively rank on my mobile device. \$\endgroup\$ Sep 18, 2021 at 0:33
  • \$\begingroup\$ @mickmackusa I put all the slots for each specific date in a timeline with fillTimelineWithTimeslot(). I then process only timelines, combining all the timelines into one with timeline_intersect(), and only at the end I convert the one timeline back to slots with extractTimeslotsFromTimeline(). Yes, I think you might have misunderstood the purpose. No problem. The PHP Fiddle was only supplied for your convenience, you're free to execute the code any other way you can. \$\endgroup\$ Sep 18, 2021 at 7:54
  • \$\begingroup\$ I think I understand now. Thanks. \$\endgroup\$ Sep 18, 2021 at 8:12

3 Answers 3

3
\$\begingroup\$

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 arrays1. 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 construct2 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.

\$\endgroup\$
3
  • \$\begingroup\$ Thank you for your answer. No complaints about the general approach? I agree that the use of the constants seem to be inverted. The use of array_fill() in newTimeline() is a very nice improvement. I completely missed that since PHP 7.1 we can assign to an array. That does look better. Yes, the for loop is rather long, and using variables, for the two toQuarters(), is probably best for readability. \$\endgroup\$ Sep 16, 2021 at 7:28
  • \$\begingroup\$ You're welcome! I updated my answer- the approach seems fine. I've been using destructuring assignment with arrays in JS but haven't been doing it much in PHP though I noticed yesterday my PHPStorm converted a few places automatically - otherwise I might not have thought of that. \$\endgroup\$ Sep 16, 2021 at 15:43
  • 1
    \$\begingroup\$ Yes, the constants I use don't need to be strings, two booleans would do. I am sure there are others ways to solve this problem. The whole idea of those timelines seems inefficient, especially if you need to be accurate to the minute. It is a very simple approach though. \$\endgroup\$ Sep 16, 2021 at 17:13
2
\$\begingroup\$

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
    )
);
\$\endgroup\$
10
  • \$\begingroup\$ Ah, yes, that looks like a big improvement. Nice use of array_map(), and I have never seen this construction: foreach ($common as [&$commonStart, &$commonEnd]). I didn't know that was possible, but it makes sense. Starting out with the timeslots of the first date and then filtering them using all the timeslots also seems like a goof idea, however, I see a problem there. What if the timeslots of one date split a "common" timeslot in two? It doesn't happen with the example data I gave, but it could. \$\endgroup\$ Sep 18, 2021 at 13:54
  • \$\begingroup\$ For instance, if I add an extra free timeslot to the last day, let's say '18:30-18:45'. Then your algorithm would ignore that, when it shouldn't. I'm sure something can be done about that. You're very close. I hope you can understand it has to be able to work for all valid input cases. I really like what you've done so far. \$\endgroup\$ Sep 18, 2021 at 13:56
  • \$\begingroup\$ Good catch. I'll revisit. \$\endgroup\$ Sep 18, 2021 at 21:41
  • \$\begingroup\$ Hmm... I am also realizing that you have variable length time expressions. Are you in control of the input formatting? Can you pad with zeros in advance ir does this code need to prepare the times? This doesn't work as I hoped: 3v4l.org/Z90OW but I could also compare integers 3v4l.org/lD3bm \$\endgroup\$ Sep 18, 2021 at 22:10
  • 1
    \$\begingroup\$ Yes, I can control the input format. However, I would use the integers, because that always works, leading zero or not. \$\endgroup\$ Sep 18, 2021 at 22:50
2
\$\begingroup\$

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.

\$\endgroup\$
6
  • \$\begingroup\$ When checking for array emptiness, if (count($array) > 0) is the same as if ($array). \$\endgroup\$ Sep 19, 2021 at 10:38
  • 1
    \$\begingroup\$ @mickmackusa Yes, that's true, but the whole line is not needed, because foreach will work with an empty array, it will just do nothing. \$\endgroup\$ Sep 19, 2021 at 10:39
  • \$\begingroup\$ A cool assignment while destructuring trick: 3v4l.org/46ChD maybe not intuitive enough? \$\endgroup\$ Sep 19, 2021 at 10:49
  • \$\begingroup\$ @mickmackusa It works, but I don't think it's a great improvement over the box-standard foreach. It basically does the same thing. As you might have noticed, I tend to be rather verbose, in my code, and prefer simple over clever. That makes it easier when I have to understand my own code in a couple of years time. \$\endgroup\$ Sep 19, 2021 at 10:56
  • \$\begingroup\$ Yes, I made my own answer the accepted answer. I think it is the best code, however, I want to thank mickmackusa and Sᴀᴍ Onᴇᴌᴀ♦ who have inspired me. \$\endgroup\$ Sep 20, 2021 at 15:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.