Что я до сих пор: Пример тестирования
$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:05:00", "duration" => "300"); // 10 mins function returnClosestTime($alreadyChosenDates, $dates){ // Set an array called $closestTime that has the time difference and the key $closestTime = [null, null]; // Check each element in array foreach($dates as $key => $date){ foreach($alreadyChosenDates as $chosenDates){ // Calculate difference between already chosen dates array and the dates array $diff = (strtotime($chosenDates["date"]) + $chosenDates["duration"]) - strtotime($date["date"]); if($diff < 0) $diff = $diff * -1; // If $closestTime is empty, populate it if($closestTime[0] === null) $closestTime = [$diff, $key]; // If $closestTime isn't empty and the current date's time difference // is smaller, populate $closestTime with the time difference and key else if($diff < $closestTime[0]) $closestTime = [$diff, $key]; } } return $dates[$closestTime[1]]; } $alreadyChosenDates[] = returnClosestTime($alreadyChosenDates, $dates); echo "<pre>"; print_r($alreadyChosenDates); echo "</pre>"; Я ищу помощь, чтобы адаптировать мой текущий код, чтобы он проходил через массив $dates date, собирающий самые ранние времена, однако время должно быть в состоянии соответствовать одному и тому же. Это нужно всегда работать с одним уже установленным. В моем примере кода у меня есть 2016-02-18 02:05:00 с длительностью 300 .
Ожидаемый результат, основанный на приведенном выше примере кода:
// Already chosen date..... Array ( [0] => Array ( [date] => 2016-02-18 02:05:00 [duration] => 300 ) ) // After first loop Array ( [0] => Array ( [date] => 2016-02-18 02:05:00 [duration] => 300 ) [1] => Array ( [date] => 2016-02-18 02:10:00 [duration] => 600 ) ) // Next loop Array ( [0] => Array ( [date] => 2016-02-18 02:05:00 [duration] => 300 ) [1] => Array ( [date] => 2016-02-18 02:10:00 [duration] => 600 ) [2] => Array ( [date] => 2016-02-18 02:20:00 [duration] => 600 ) ) // Next loop Array ( [0] => Array ( [date] => 2016-02-18 02:05:00 [duration] => 300 ) [1] => Array ( [date] => 2016-02-18 02:10:00 [duration] => 600 ) [2] => Array ( [date] => 2016-02-18 02:20:00 [duration] => 600 ) [3] => Array ( [date] => 2016-02-18 02:30:00 [duration] => 600 ) )
Другой пример с другим временем начала:
// Already chosen date..... Array ( [0] => Array ( [date] => 2016-02-18 02:25:00 [duration] => 300 ) ) // After first loop Array ( [0] => Array ( [date] => 2016-02-18 02:25:00 [duration] => 300 ) [1] => Array ( [date] => 2016-02-18 02:30:00 [duration] => 600 ) ) // Next loop Array ( [0] => Array ( [date] => 2016-02-18 02:25:00 [duration] => 300 ) [1] => Array ( [date] => 2016-02-18 02:30:00 [duration] => 600 ) [2] => Array ( [date] => 2016-02-18 02:15:00 [duration] => 300 ) ) // Next loop Array ( [0] => Array ( [date] => 2016-02-18 02:25:00 [duration] => 300 ) [1] => Array ( [date] => 2016-02-18 02:30:00 [duration] => 600 ) [2] => Array ( [date] => 2016-02-18 02:15:00 [duration] => 300 ) [3] => Array ( [date] => 2016-02-18 02:05:00 [duration] => 300 ) )
Входные данные:
1) с учетом списка «выбранных» дат 2) Список дат кандидата
Результат: 1) «Окончательный список« неперекрывающихся »дат
Где:
a) Первые «выбранные» данные являются «стартовой» датой, т.е. все даты кандидата должны быть не позднее или после этой даты.
b) Никакие диапазоны дат не должны перекрываться.
1) setter s при условии:
`setChosen(array $chosenDates)` `setCandidates(array $candidateDates)`
2) Исправлены случаи сбоя отсутствующих входов.
3) Передача массивов через constructor является необязательной.
Демонстрация: https://eval.in/678371
Источник класса : http://pastebin.com/K81rfytB
brute force всех дат в пределах заданного диапазона дат. todo: преобразовать «поиск грубой силы» в «динамическое программирование»; добавив «memoization». Это не должно быть трудно сделать, поскольку в настоящее время используется «дерево решений».
Я обновлю этот ответ с инструкциями позже. Теперь см. Ссылку «demo» выше.
Демонстрация:
Данные, предоставленные пользователем, и результаты на странице «eval.in»
Обновлено с сеттерами и обработкой края
Если списки сортируются по «дате начала», то довольно легко рассуждать о списке дат.
a) Первая дата начала после даты «выбранного старта» должна быть самой близкой.
Я могу сразу определить, overlaps ли следующая дата с уже выбранными.
Таким образом, сортировка списков полезна.
Чтобы сделать код, который проверяет перекрытие, я решил преобразовать даты кандидатов в стандартный формат, который включает в себя «диапазон» или window каждого «кандидата» как «секунды эпохи (временная отметка unix)». Это делает тесты более ясными?
Вывод не должен содержать совпадающих дат кандидата .
Это то, что предоставляет класс.
ScheduleList ), который выполняет всю работу /* --------------------------------------------------------------------------------- * Class that does all the work... */ /* * Requirements: * * Input: * 1) given a list of 'chosen' dates * 2) A list of 'candidate' dates * * Output: * 1) A 'final list of 'none-overlapping' dates * * Where: * a) The first 'chosen' data is a 'start' date * ie All candidate dates must be on or after this date. * * b) No date ranges must ovevlap. */ 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 */ public $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 */ public $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(), array $candidateDates = array()) { if (!empty($chosenDates)) { $this->setChosen($chosenDates); } if (!empty($candidateDates)) { $this->setCandidates($candidateDates); } } /** * Convert chosen dates to date range and sort them * * @param array $chosenDates */ public function setChosen(array $chosenDates) { // 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']; }); } } /** * setter for candidates - will convert to date range * * @param array $candidateDates * * @return void; */ public function setCandidates(array $candidateDates) { // 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() { if (empty($this->chosen) && empty($this->candidates)) { throw new \Exception('Generate Schedule: no input provided: ', 500); } $this->final = $this->chosen; // 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. */ public 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 (!empty($this->chosen) && $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('Ymd 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('Ymd H:i:s'), ' len: ', $when['duration'], ' end: ', date('Ymd 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; } }
ScheduleList , передав chosen массив и массив «date». generateList(); метод вернет «окончательный» неперекрывающийся массив дат. Код:
$datesListGenerator = new ScheduleList($alreadyChosenDates, $dates); $final = $datesListGenerator->generateList();
$datesListGenerator = new ScheduleList(); $datesListGenerator->setChosen($alreadyChosenDates); $datesListGenerator->setCandidates($dates);
var_dump('public makeDateRange : ', $datesListGenerator->makeDateRange(array('date' => '2016-04-01 08:09:10', 'duration' => 1))); array (size=4) 'when' => object(DateTime)[83] public 'date' => string '2016-04-01 08:09:10' (length=19) public 'timezone_type' => int 3 public 'timezone' => string 'UTC' (length=3) 'duration' => int 1 'startTime' => int 1459498150 'endTime' => int 1459498151
код:
echo PHP_EOL, PHP_EOL, 'Final List'; foreach ($final as $when) { $datesListGenerator->displayWhen($when); },echo PHP_EOL, PHP_EOL, 'Final List'; foreach ($final as $when) { $datesListGenerator->displayWhen($when); }
вывод:
Final List date: 2016-02-18 02:05:00 len: 300 end: 2016-02-18 02:10:00 start: 1455761100 end: 1455761400 date: 2016-02-18 02:10:00 len: 600 end: 2016-02-18 02:20:00 start: 1455761400 end: 1455762000 date: 2016-02-18 02:20:00 len: 600 end: 2016-02-18 02:30:00 start: 1455762000 end: 1455762600 date: 2016-02-18 02:30:00 len: 600 end: 2016-02-18 02:40:00 start: 1455762600 end: 1455763200
Код:
echo PHP_EOL, PHP_EOL, 'Unused List'; echo PHP_EOL, 'will be before first Chosen or Overlaps with one in the final list...', PHP_EOL; foreach ($datesListGenerator->getUnused() as $when) { $datesListGenerator->displayWhen($when); },echo PHP_EOL, PHP_EOL, 'Unused List'; echo PHP_EOL, 'will be before first Chosen or Overlaps with one in the final list...', PHP_EOL; foreach ($datesListGenerator->getUnused() as $when) { $datesListGenerator->displayWhen($when); }
Вывод:
Unused List will be before first Chosen or Overlaps with one in the final list... date: 2016-02-18 02:00:00 len: 600 end: 2016-02-18 02:10:00 start: 1455760800 end: 1455761400 date: 2016-02-18 02:05:00 len: 300 end: 2016-02-18 02:10:00 start: 1455761100 end: 1455761400 date: 2016-02-18 02:15:00 len: 300 end: 2016-02-18 02:20:00 start: 1455761700 end: 1455762000 date: 2016-02-18 02:25:00 len: 300 end: 2016-02-18 02:30:00 start: 1455762300 end: 1455762600