How to push the next date/time to array which fits around current date/times in array?

Question

What I have so far: Example to test

$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>";

I am looking for help to adapt my current code so that it loops through the $dates array picking the earliest times however the times need to be able to fit around one and other. This needs to always work with one $alreadyChosenDates already picked. In my example code I've got 2016-02-18 02:05:00 with duration of 300.

Expected outcome based on example code above:

// 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
        )
)

Another example with different start time:

// 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
        )
)

Answer 1

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 i.e. All candidate dates must be on or after this date.

b) No date ranges must overlap.

Update 1 - Provide 'Setter's and Process 'edge cases

1) setters provided :

`setChosen(array $chosenDates)`

`setCandidates(array $candidateDates)`

2) Edge cases of missing inputs tested for.

3) Passing arrays via the constructor is optional.

Update 2 - Search for a list of optimal non-overlapping dates within a date range.

Demonstration: https://eval.in/678371

Class source: http://pastebin.com/K81rfytB

• It finds the list by doing a brute force search of all the dates within a given date range.

todo: convert the 'brute force search' to 'dynamic programing; by adding 'memoization'. It should not be difficult to do as it uses a 'decision tree' currently.

I will update this answer with instructions about is later. For now see the 'demo' link above.

Original Answer

Demonstration:

• User supplied data and the results at 'eval.in'

• Updated with setters and edge case processing

Explanation (or how I thought about it)

If the lists are sorted by 'start date' then it is quite easy to reason about the list of dates.

a) The first start date after the 'chosen start' date must be the closest.

I can immediately detect whether the next date overlaps with ones already selected.

So, Sorting the lists is useful.

To make the code which checks for overlapping easier I decided to convert the candidate dates' to a standard format that includes the 'range' or window of each 'candidate' as 'epoch seconds (unix timestamp)'. It makes the tests clearer?

The output must not contain any overlapping candidate dates.

That is what the class provided does.

the Class (ScheduleList) that does all the work

/* ---------------------------------------------------------------------------------
 * 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
 *              i.e. 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('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;
    }
} 

Run it

• Create an instance of the ScheduleList by passing the chosen array and the 'dates' array.
• The generateList(); method will return the 'final' none-overlapping dates array.

Code:

$datesListGenerator = new ScheduleList($alreadyChosenDates,
                                       $dates);
$final = $datesListGenerator->generateList();

Update: Run with 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 (none-overlapping with any candidate input)

code:

echo PHP_EOL, PHP_EOL, 'Final List';
foreach ($final as $when) {
    $datesListGenerator->displayWhen($when);
}

output:

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

Unused (Before start or Overlap)

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