3v4l.org

run code in 200+ php & hhvm versions
Bugs & Features
<?php $dates[] = array("date" => "2016-02-18 02:00:00", "duration" => "600"); // 10 mins $dates[] = array("date" => "2016-02-18 02:05:00", "duration" => "300"); // 5 mins $dates[] = array("date" => "2016-02-18 02:10:00", "duration" => "600"); $dates[] = array("date" => "2016-02-18 02:15:00", "duration" => "300"); $dates[] = array("date" => "2016-02-18 02:20:00", "duration" => "600"); $dates[] = array("date" => "2016-02-18 02:25:00", "duration" => "300"); $dates[] = array("date" => "2016-02-18 02:30:00", "duration" => "600"); $alreadyChosenDates[] = array("date" => "2016-02-18 02:10:00", "duration" => "600"); class ScheduleList { /** * A list of all the dates that: * 1) After the 'chosen' start date * 2) Do not overlap with any 'chosen' date * * @var array $candidates */ private $candidates = array(); /** * Any date record we didn't use. * * @var array $unused */ private $unused = array(); /** * List of dates that must be included in the 'final' list. * The earliest date is assumed to be a start date and everything must be later. * * @var array $chosen */ private $chosen = array(); /** * Ordered list of `none overlapping' dates from the chosen and candidates * * @var array $final */ private $final = array(); /** * These are the date lists. * They will be converted, sorted and filters as required. * * @param array $chosenDates * @param array $candidateDates * @return void */ public function __construct(array $chosenDates, array $candidateDates) { // convert and sort foreach ($chosenDates as $when) { $this->chosen[] = $this->makeDateRange($when); } if (count($this->chosen) > 1) { // sort them so we can easily compare against them usort($this->chosen, function ($when1, $when2) { return $when1['startTime'] - $when2['startTime']; }); } // add chosen to the final list $this->final = $this->chosen; // convert, sort and filter the candidates $this->convertCandidates($candidateDates); } /** * Add the candidates to the final list * * Known conditions: * o Both lists are in start date order * o No candidates overlap with any chosen date * o The candidates may overlap with each other - Hmm... need to check... * * Note: The '$this->isOverlapsAny' method - as it is used a lot will be expensive (O(n^2)) * I can think of ways to reduce that - will happen when it is refactored ;-/ * * @return array */ public function generateList() { // first candidate MUST be the closest to the first chosen date due to sorting. $this->final[] = array_shift($this->candidates); // move it to the final list // Add the remaining candidates checking for overlaps as we do so... foreach ($this->candidates as $candidate) { if ($this->isOverlapAny($candidate, $this->final)) { $this->unused[] = $candidate; } else { $this->final[] = $candidate; } } // sort final by start times - makes it easy to reason about usort($this->final, function ($when1, $when2) { return $when1['startTime'] - $when2['startTime']; }); return $this->final; } /* * Convert each date to a dateRange that is easier to check and display * * o Check each candidate date for ovelapping with any of the 'chosen dates' * o Check if before first chosen start data. */ protected function convertCandidates(array $candidateDates) { foreach ($candidateDates as $idx => $when) { $candidate = $this->makeDateRange($when); // overlaps with any chosen then ignore it if ($this->isOverlapAny($candidate, $this->chosen)) { // ignore it $this->unused[] = $candidate; // record failed ones so easy to check continue; } // ignore if before first chosen start time if ($candidate['endTime'] <= $this->chosen[0]['startTime']) { $this->unused[] = $candidate; // record failed ones so easy to check continue; } $this->candidates[] = $candidate; } // sort candidates by start times - makes it easy to reason about usort($this->candidates, function ($when1, $when2) { return $when1['startTime'] - $when2['startTime']; }); } /** * Convert to UNIX timestamp as seconds will make the calculations easier * * The result has: * 1) the time as a date object - I can do calculations / format it whatever * 2) startTime as epoch seconds * 3) endTime as epoch seconds * * @param array $when * * @return array */ public function makeDateRange(array $when) { $dt = \DateTime::createFromFormat('Y-m-d H:i:s', $when['date']); $result = array(); $result['when'] = $dt; $result['duration'] = (int) $when['duration']; $result['startTime'] = (int) $dt->format('U'); $result['endTime'] = (int) $result['startTime'] + $when['duration']; return $result; } /** * if start is after other end OR end is before other start then they don't overlap * * Easiest way is to check that they don't overlap and reverse the result */ public function isOverlap($when1, $when2) { return ! ( $when1['endTime'] <= $when2['startTime'] || $when1['startTime'] >= $when2['endTime']); } /** * Check if candidate overlaps any of the dates in the list * * @param array $candidate * @param array $whenList -- list of non-overlapping dates * * @return boolean true if overlaps */ function isOverlapAny($candidate, $whenList) { foreach ($whenList as $when) { if ($this->isOverlap($when, $candidate)) { // ignore it return true; } } return false; } /** * Show a date formatted for debugging purposes * * @param array $when * @return void */ public function displayWhen(array $when) { echo PHP_EOL, 'date: ', $when['when']->format('Y-m-d H:i:s'), ' len: ', $when['duration'], ' end: ', date('Y-m-d H:i:s', $when['endTime']), ' start: ', $when['startTime'], ' end: ', $when['endTime']; } /* * `Getters` so you can see what happened */ public function getChosen() { return $this->chosen; } public function getUnused() { return $this->unused; } public function getCandidates() { return $this->candidates; } public function getFinal() { return $this->final; } /** * properties - for those of us that like them */ public function __get($name) { if (property_exists($this, $name)) { return $this->$name; } return null; } } $datesListGenerator = new ScheduleList($alreadyChosenDates, $dates); $final = $datesListGenerator->generateList(); foreach ($datesListGenerator->getUnused() as $when) { $datesListGenerator->displayWhen($when); }
based on YODbj
Output for 5.6.0 - 7.3.0alpha1
date: 2016-02-18 02:00:00 len: 600 end: 2016-02-18 02:10:00 start: 1455757200 end: 1455757800 date: 2016-02-18 02:05:00 len: 300 end: 2016-02-18 02:10:00 start: 1455757500 end: 1455757800 date: 2016-02-18 02:10:00 len: 600 end: 2016-02-18 02:20:00 start: 1455757800 end: 1455758400 date: 2016-02-18 02:15:00 len: 300 end: 2016-02-18 02:20:00 start: 1455758100 end: 1455758400 date: 2016-02-18 02:25:00 len: 300 end: 2016-02-18 02:30:00 start: 1455758700 end: 1455759000