PHP: I have an assoc array with time ranges ($k=>$v integers), I want to trim and combine overlapping schedules

Question

Premise: I'm working at a project that needs to be PHP 5.2 compliant, I cannot use PHP 5.3+ DateInterval or other PHP>=5.3-only instructions, regrettably.

I have an array that contains business hours expressed as $k => $v ranges, so the key is a start, the value is an end, like so:

array( 
    09:00 => 11:30
    09:30 => 11:00
    10:00 => 12:30
    13:30 => 14:30   
)

In this example we have the first three pairs of ranges that overlap, I could express the same thing as 09:00 => 12:30 (meaning: opens at 9 am, closes at 12.30 pm), since the start and end of the first three pairs overlap.

I could also write the array like so, as integers (or I could use floats e.g. 09:30 becomes 9.3 it doesn't matter I think):

array( 
     900 => 1130
     930 => 1100
    1000 => 1230
    1330 => 1430   
)

How to turn the array into:

array(
     900 => 1230
    1330 => 1430
)

Ideas that come to my mind are looping the array, using array_slice, passing values by reference and unset() things while at it... But I'm not sure if that would be the best idea or I'm just overcomplicating it.

Answer 1

There are many solutions to this problem; here's mine:

http://phpfiddle.org/main/code/batv-hzqw

Hopefully it is clear enough and fulfills the criteria that you have laid out -- If not please do tell me :)

Answer 2

One way to do this type of overlap checking is to use this algorithm truth: What's the most efficient way to test two integer ranges for overlap?

Pseudo code

1. Loop through all of your time ranges and put them into the same bucket if they overlap.

2. Break those buckets down into single elements with the lowest start and highest end time.

PHP example:

<?php

$times = array( 
     900 => 1130,
     930 => 1100,
    1000 => 1230,
    1330 => 1430,
     845 => 900,
    1330 => 1700,
     845 => 1000   
);


function reduceOverlap($times) {

    $reduced = array();

    //Put the first entry into our final bucket
    $reduced[array_keys($times)[0]] = $times[array_keys($times)[0]];

    foreach ($times as $start => $end) {

        // Trip this flag if a new bucket does not need to be created
        $foundOverlap = false;

        // Check if this time can go in one of our buckets
        foreach ($reduced as $reducedStart => $reducedEnd) {

            // Truthy check for overlap of time range with bucket range
            if ($start <= $reducedEnd && $end >= $reducedStart) {

                // Use this for start key incase it gets changed
                $startKey = $reducedStart;

                // Was the start less than the bucket's start? 
                // If yes update bucket's start time
                if ($start < $reducedStart) {
                    unset($reduced[$reducedStart]);
                    $reduced[$start] = $reducedEnd;
                    $startKey = $start;
                }

                // Was the end greater than the bucket's end?
                // If yes update bucket's end time
                if ($end > $reducedEnd) {
                    $reduced[$startKey] = $end;
                }

                $foundOverlap = true;
            }
        }

        // There was no overlap, create a new bucket
        if (!$foundOverlap) {
            $reduced[$start] = $end;
        }
    }

    return $reduced;
}

var_dump(reduceOverlap($times));

Output:

array(2) {
  [1330]=>
  int(1700)
  [845]=>
  int(1230)
}