3
\$\begingroup\$

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-171

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?


1https://stackoverflow.com/q/41150768/1575353

\$\endgroup\$
2
  • 2
    \$\begingroup\$ 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). \$\endgroup\$
    – J_H
    Sep 6, 2017 at 22:42
  • 2
    \$\begingroup\$ @JH Comments are for seeking clarification to the question, and may be deleted. Please put all suggestions for improvements in answers. \$\endgroup\$ Sep 6, 2017 at 23:42

1 Answer 1

1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

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

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