Group time intervals together

Question

A while back, I supplied an answer on SO for grouping time intervals together.

Say you have an array like this:

$timeslots[] = ['start' => '09:00:00', 'end' => '10:00:00'];
$timeslots[] = ['start' => '10:00:00', 'end' => '11:00:00'];
$timeslots[] = ['start' => '11:00:00', 'end' => '12:00:00'];
$timeslots[] = ['start' => '13:00:00', 'end' => '14:00:00'];
$timeslots[] = ['start' => '15:00:00', 'end' => '16:00:00'];
$timeslots[] = ['start' => '16:00:00', 'end' => '17:00:00'];
$timeslots[] = ['start' => '17:00:00', 'end' => '18:00:00'];

How would you go about processing this array to achieve the following end result:

09-11, 13, 15-17

This end result basically represents the shortest possible overview of which slots are available and grouping consecutive slots (where currentItem.EndHour == nextItem.startHour)

Now, intervals will always be the same within a slot, but the gaps can be completely random. To illustrate, the array might just as well look like this:

$timeslots[] = ['start' => '10:30:00', 'end' => '11:30:00'];
$timeslots[] = ['start' => '11:30:00', 'end' => '12:30:00'];
$timeslots[] = ['start' => '14:00:00', 'end' => '15:00:00'];
$timeslots[] = ['start' => '15:00:00', 'end' => '16:00:00'];
$timeslots[] = ['start' => '16:00:00', 'end' => '17:00:00'];
$timeslots[] = ['start' => '17:00:00', 'end' => '18:00:00'];

The intended result for this array would be: 10:30 - 11:30, 14-17¹

My solution was to "create an array with the start time being the key and the value being an array with the end time and the start time, though if we find that the start time exists in the array as the end time for another element, we update that existing element."

function combine($timeslots) {
    $outputs = array();
    foreach($timeslots as $timeslot) {
        $startToCombine = null;
        foreach($outputs as $start=>$output) {
            if ($output['end'] == $timeslot['start']) {
                $startToCombine = $start;
                break;
            }
        }
        if ($startToCombine) {
            $outputs[$startToCombine]['end'] = $timeslot['end'];
            $outputs[$startToCombine]['lastStart'] = $timeslot['start'];
        }
        else {
            $outputs[$timeslot['start']] = array(
                'lastStart' => $timeslot['start'],
                'end' => $timeslot['end']
            );
        }
    }
    return implode(', ', array_map(function($start) use ($outputs) {
        if ($outputs[$start]['lastStart'] != $start) {
            return $start.'-'.$outputs[$start]['lastStart'];
        }
        return $start;
    },array_keys($outputs)));
}

See it in action on Teh Playground.

What would you do differently, perhaps for readability, performance, etc.? Would you take a completely different approach altogether?

Update 10/6/2017

Taking the suggestion by J H, i.e. "You're doing a linear scan through an array. You'd be happier if you were doing hashed \$O(1)\$ time lookups in a set (or map).", I have updated the code to use the end time as the index of the output array (i.e. the hash map). Also, I have incorporated more functional techniques (beyond array_map()) and used array_reduce() to iterate through the timeslots.

By using the end time as the index, the code will look for that end time in the array and if it exists, then combine it, setting the last start time, moving the combined timeslot to have the index of the new end time and un-setting the timeslot at the previous end time.

Then when outputting the times, the keys don't need to be considered for the output, since the output only needs the start times. A great advantage of this is the need for referencing $outputs via the use statement within the lambda function is eliminated since we aren't iterating over the keys anymore.

function combine($timeslots) {
    $outputs = array_reduce($timeslots, function($outputs, $timeslot) {
        if (array_key_exists($timeslot['start'], $outputs)) {
            $timeslotToCombine = $outputs[$timeslot['start']];
            $timeslotToCombine['lastStart'] = $timeslot['start'];
            $outputs[$timeslot['end']] = $timeslotToCombine;
            unset($outputs[$timeslot['start']]);
        }
        else {
            $outputs[$timeslot['end']] = array(
                'start' => $timeslot['start']
                );
        }
        return $outputs;
    }, array());
    return implode(', ', array_map(function($timeslot) {
        if (array_key_exists('lastStart', $timeslot)) {
            return $timeslot['start'].'-'.$timeslot['lastStart'];
        }
        return $timeslot['start'];
    },$outputs));
}

For a demonstration of this, checkout this playground example.

Are there any other improvements you can think of?

---

¹_{https://stackoverflow.com/q/41150768/1575353}

Answer 1

If I were you (and I am) I would take the suggestion by J H, i.e. "You're doing a linear scan through an array. You'd be happier if you were doing hashed O(1) time lookups in a set (or map)." and use the end time as the index of the output array (i.e. the hash map). Also, let us build on functional techniques (beyond array_map()) and use array_reduce() to iterate through the timeslots.

By using the end time as the index, we can look for that end time in the array and if it exists, then combine it, setting the last start time, moving the combined timeslot to have the index of the new end time and un-setting the timeslot at the previous end time.

Then when outputting the times, we don't need to worry about the keys, since we output the start times only. A great advantage of this is the need for referencing $outputs via the use statement within the lambda function is eliminated since we aren't iterating over the keys anymore.

function combine($timeslots) {
    $outputs = array_reduce($timeslots, function($outputs, $timeslot) {
        if (array_key_exists($timeslot['start'], $outputs)) {
            $timeslotToCombine = $outputs[$timeslot['start']];
            $timeslotToCombine['lastStart'] = $timeslot['start'];
            $outputs[$timeslot['end']] = $timeslotToCombine;
            unset($outputs[$timeslot['start']]);
        }
        else {
            $outputs[$timeslot['end']] = array(
                'start' => $timeslot['start']
                );
        }
        return $outputs;
    }, array());
    return implode(', ', array_map(function($timeslot) {
        if (array_key_exists('lastStart', $timeslot)) {
            return $timeslot['start'].'-'.$timeslot['lastStart'];
        }
        return $timeslot['start'];
    },$outputs));
}

For a demonstration of this, checkout this playground example.