Split a time range into pieces by other time ranges

Question

I have a complicated task that I have been beating my head against the wall now for a few days. I've tried about 4 different approaches, however each seems to stall and it is becoming extremely frustrating.

I have a time range. For example, 14:30:00 until 18:30:00. Consider this time range somebody's work shift. During this time range, they state they cannot work from 15:30:00 until 16:30:00 and from 17:30:00 until 18:30:00. I need to modify the original shift's start and end times to remove the conflicting shifts.

The original shift array looks like this:

$original_shift[0]['start'] = '14:30:00';
$original_shift[0]['end']   = '18:30:00';

And the time ranges to be removed from the original shift look like this:

$subshift[0]['start'] = '15:30:00';
$subshift[0]['end']   = '16:30:00';
$subshift[1]['start'] = '17:30:00';
$subshift[1]['end']   = '18:30:00';

Here is a visualization:

So, I basically need my original shift to look like this when I'm done:

$original_shift[0]['start'] = '14:30:00';
$original_shift[0]['end']   = '15:30:00';
$original_shift[1]['start'] = '16:30:00';
$original_shift[1]['end']   = '17:30:00';

Some complications that I also need to consider are:

1. These time ranges may be any times (not constrained to the half hour as I have used in my example), however I will know with 100% certainty the the unavailable time ranges will always start and end on or in between the original shift's start and end times.

2. Unavailable times may butt up and/or take the entire original shift's time up.

I'm not looking for someone to "write my code" as much as I am looking for someone who has dealt with something like this in the past and may have some insight on how they accomplished it.

Answer 1

As you specifically asked for "some insight" rather than a full working answer, I'd personally go with arrays populated with "minutes".

$shift = array(
    'start' => '15:30:00',
    'end' => '18:30:00',

    'original' => array(),
    'unavailable' => array(),
    'modified' => array()
);

You'd then do some jiggery pokery to convert 15:30:00 into 930 and 18:30:00 into 1110 (number of minutes) which will give you the difference between start and end times.

Use range() to quickly fill up the original array, load in your unavailable in a similar format and then use things like array_intersect() and array_diff() to work out which minutes from the original shift are unavailable.

From that, build up the modified array, and read directly from there to your output.

Answer 2

You need to do calculations of time-ranges. As the image shows this seems like a simple subtraction. It would be nice to just have objects that do these.

I had no code for this ready, so the following concept is a bit rough although probably not that bad.

A Range type that represents a time from-to. Those are as DateTime so that the benefits of these existing types can be used. I didn't use much of the benefits so far, however for the rest of the application this can make sense.

The Range type already contains some basic comparison methods I thought were useful to do parts of the calculations.

However as an object can not divide itself into two I also created a Ranges type which can represent one or more Ranges. This was necessary to have something that can be "divided".

I cheated a little here because I implemented the difference calculation as a member of Range, returning an array with one or multiple Range objects. The final calculation then is just having a shift and substract the unavailable ranges from it:

$shift = new Ranges(new DateTime('14:30:00'), new DateTime('18:30:00'));

$unavailables = new Ranges([
    new Range(new DateTime('15:30:00'), new DateTime('16:30:00')),
    new Range(new DateTime('17:30:00'), new DateTime('18:30:00')),
]);

$shift->subtract($unavailables);

The shift then spans:

14:30:00 - 15:30:00
16:30:00 - 17:30:00

Demo; Gist

I can not say if it is worth the abstraction, what is nice with DateTime objects is that you can compare them with >, < and =. The real benefit from these classes might shed into light when you need more calculations between Range and Ranges. Maybe the interface is not sweet yet, however the basic calculations behind are outlined in the code already.

One caveat: The difference between 14:00-15:00 and 14:00-15:00 in my code will result to 14:00-14:00. I keep the start time to not run empty, but you can run empty, too. The Ranges object should handle it nicely.

Answer 3

The code should speak for itself:

$original_shift[0]['start'] = '14:30:00';
$original_shift[0]['end'] = '18:30:00';

$breaks[0]['start'] = '14:30:00';
$breaks[0]['end'] = '15:30:00';
$breaks[1]['start'] = '16:30:00';
$breaks[1]['end'] = '17:30:00';

$modified_shift = array(
    array('start' => $original_shift[0]['start'])
);

for($x = 0, $y = count($breaks), $z = 0; $x < $y; $x++){
    $modified_shift[$z]['end'] = $breaks[$x]['start'];
    if($modified_shift[$z]['end'] != $modified_shift[$z]['start']){
        $z++;       
    }
    $modified_shift[$z]['start'] = $breaks[$x]['end'];
}

$modified_shift[$z]['end'] = $original_shift[0]['end'];

if($modified_shift[$z]['end'] == $modified_shift[$z]['start']){
    unset($modified_shift[$z]);
}