Requirements
Input:
1) taking into account the list of "selected" dates 2) List of candidate dates
Conclusion: 1) "The final list of" non-overlapping "dates
Where:
a) The first "selected" data is the start date, that is, all dates of the candidate must be indicated or after this date.
b) No date ranges should overlap.
Update 1 - Providing Setter and Process Edge Cases
1) setter
provided:
`setChosen(array $chosenDates)` `setCandidates(array $candidateDates)`
2) Error margins of missing inputs checked for.
3) Passing arrays using constructor
is optional.
Update 2 - Search for a list of optimal non-overlapping dates in a date range.
Demo: https://eval.in/678371
Class source : http://pastebin.com/K81rfytB
- It finds a list by searching for
brute force
all dates within a given date range.
todo: convert "brute force search" into "dynamic programming"; adding "memoization". This should not be difficult to do, since a "decision tree" is currently being used.
I will update this answer with instructions later. For now, see the "demo" link above.
Original answer
Demonstration:
Explanation (or how I thought about it)
If lists are sorted by start date, itโs pretty easy to talk about a list of dates.
a) The first start date after the โselected startโ date should be the closest.
I can immediately determine if the next date will overlaps
with the ones already selected.
So sorting lists is useful.
To make code that checks for overlap, I decided to convert the candidate dates into a standard format that includes the "range" or window
each "candidate" as "seconds of an era (unix timestamp)." Does this make the tests clearer?
The withdrawal must not contain matching candidate dates.
This is what the class provides.
class ( ScheduleList
) that does all the work
class ScheduleList { private $candidates = array(); public $unused = array(); private $chosen = array(); public $final = array(); public function __construct(array $chosenDates = array(), array $candidateDates = array()) { if (!empty($chosenDates)) { $this->setChosen($chosenDates); } if (!empty($candidateDates)) { $this->setCandidates($candidateDates); } } public function setChosen(array $chosenDates) {
Run it
- Create an instance of
ScheduleList
by passing the chosen
array and the "date" array. - Method
generateList();
will return a "final" array with non-overlapping dates.
the code:
$datesListGenerator = new ScheduleList($alreadyChosenDates, $dates); $final = $datesListGenerator->generateList();
Update: run using setters:
$datesListGenerator = new ScheduleList(); $datesListGenerator->setChosen($alreadyChosenDates); $datesListGenerator->setCandidates($dates);
Various outputs
makeDakeRange is now a public function:
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
Final (non-overlapping with any input candidate)
the code:
echo PHP_EOL, PHP_EOL, 'Final List'; foreach ($final as $when) { $datesListGenerator->displayWhen($when); }
exit:
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
Not used (before starting or shutting down)
the code:
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); }
Output:
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