Optimal algorithm to get the next available time slot in an associative array containing sorted time slots

Question

Given a PHP associative array containing time slots like this :

$timeSlots = Array (
    "12:00:00" => "12:05:00",
    "12:10:00" => "12:15:00",
    "16:40:00" => "16:45:00",
    "16:50:00" => "17:00:00"
);

Assuming all intervals are non-overlapping and start times are all sorted in ascending order.

I want to have a function that returns the time slot available for the current time and the next available time slot. I'm assuming that all the slots are free.
i.e, lets say the time now is 16:42, then I want to return the 3rd time slot - "16:40:00" => "16:45:00" and return the next slot as "16:50:00" => "17:00:00".

What I tried is something like this which uses linear search to get the time intervals :

function searchTimeSlots ($currentTime) {
    global $timeSlots;
    $timeSlot = null;
    $getNext = false;

    // get the current time slot and next available one or just next available one if there's no current time slot
    foreach ($timeSlots as $fromTime => $toTime) {
        if ($getNext) {
            $timeSlot['next'] = Array (
                "start" => $fromTime,
                "finish" => $toTime
            );
            break;
        }
        if (($currentTime >= $fromTime) && ($currentTime < $toTime)) {
            $timeSlot = Array (
                "current" => Array (
                    "start" => $fromTime,
                    "finish" => $toTime
                )
            );
            $getNext = true;
        }else if ($currentTime < $fromTime) {
            $timeSlot = Array (
                "next" => Array (
                    "start" => $fromTime,
                    "finish" => $toTime
                )
            );
            break;
        }
    }

    // if there's no current or next slot available send the first available slot
    if ($timeSlot == null) {
        foreach ($timeSlots as $fromTime => $toTime) {
            $timeSlot = Array (
                "next" => Array (
                    "start" => $fromTime,
                    "finish" => $toTime
                )
            );
            break;
        }
    }

    return $timeSlot;
}

This's returning the array

Array
(
    [current] => Array
        (
            [start] => 16:40:00
            [end] => 16:45:00
        )

    [next] => Array
        (
            [start] => 16:50:00
            [end] => 17:00:00
        )

)

I want to know if there's a better way to get this array. Any help would be appreciated.

Answer 1

• Given a list of sorted, non-overlapping times ($timeSlots)

• When given a specific time ($timeNow)

Search the list of times quickly and return the following:

• 1) If the timeNow is within a timeSlot then return the timeSlot

• 2) If there is a valid timeSlot available immediately after the 'timeNow' then return the next valid timeSlot.

• The lookup needs to be efficient as there can be repeated calls with different specific times ('timeNow')

Thoughts

As the timeslots are a fixed number, ordered and non-ovelapping then the fastest way of finding the required one will be by using a 'binary search' on an array.

The requirement to test for the 'timeNow' to be within the range of the duration of a timeSlot is not an issue.

The requirement to identify the 'next valid timeSlot means that just the 'real timeSlots' cannot be held in the 'timeSlot' array. The 'gaps' between the 'real timeSlots' need to be recorded so that the 'binary search' will work correctly. i.e. timeNow will always be either a 'real timeSlot' or the 'gap' immediately before the 'next real timeSlot'.

Implementation

1) An ordered array of 'timeSlot' ($startTimes) where each 'timeSlot' has the following properties:

• Start time : timestamp seconds for ease of comparing and output formatting
• End Time : timestamp seconds
• 'real' : a boolean to indicate a 'real' timeSlot of a 'gap' between timeSlots

I decided to put all the code in a class (TimeRanges) as there are conversions to be done from input to internal formats. Also, the input timeSlots only need to be converted in startTimes once.

Output

• an array with zero, one or two 'timeSlot' entries.

Demonstration (with test data) at eval.in

Class: TimeRanges source

TimeRanges

class TimeRanges {

  /**
   * need this for binary search
   */     
  private $startTimes = array(); 
  private $lastSlotIdx = 0;

  // outputs so you don't need to run the search again

  private $timeNow = 0;
  private $outSlots = array();  

  private $dateWhen = null; // used to convert seconds to different formats

  /**
   * @param array The timeSlots that will be searched
   */     
  public function __construct(array $timeSlots) {
      $this->buildAllstartTimes($timeSlots);
      $this->dateWhen = new \DateTime();
  }

  /**
   * Create a list of real and 'virtual' timeslots.  
   * i.e. All gaps between the real timeslots we treat as a timeslot 
   *      when searching for a matching timeslot   
   */     
  protected function buildAllStartTimes($timeSlots) {

      $this->startTimes = array();

      $iter = new ArrayIterator($timeSlots); 

      $prvEndTime = PHP_INT_MAX; // needed to identify 'gaps'

      while ($iter->valid()) {

          $curStartTime = $this->asSeconds($iter->key());   // seconds
          $curEndTime = $this->asSeconds($iter->current()); // so is easy to check

          if ($curStartTime > $prvEndTime) { // make a 'gap' timeslot
              $this->startTimes[]  = ['s' => $prvEndTime + 1,
                                      'e' => $curStartTime,
                                      'real' => false];
              $prvEndTime = $curStartTime;

          } else { // is real
              $this->startTimes[] = ['s' => $curStartTime,
                                     'e' => $curEndTime,
                                     'real' => true];
              $prvEndTime = $curEndTime;
              $iter->next();           
          }          
      }
      $this->lastSlotIdx = count($this->startTimes) - 1;
  }

  /**
   *  Search the array using a modifield binary search
   *  
   *  This can return zero, one or two 'real' timeslots:      
   *  
   *  o timeNow before first timeslot -- return first timeslot
   *  o timeNow after last timeslot   -- return empty array
   *  o timeNow on a 'gap'            -- return one timeslot (the next one)     
   *      
   * @param string current time 
   */        
  public function findTimeSlots($timeNow) {
      $this->timeNow = $this->asSeconds($timeNow); 
      $startSlotIdx = $this->searchStartTimes($this->timeNow, 0, $this->lastSlotIdx);      


      $returnedSlots = 1;
      if ($startSlotIdx > $this->lastSlotIdx ) { 
          $returnedSlots = 0;

      } elseif (    isset($this->startTimes[$startSlotIdx])  
                 && $this->startTimes[$startSlotIdx]['real']) { 

          $returnedSlots = 2;
      } 


      $out = array();  // need current and next real timeslots in the array    
      for ($numSlots = $returnedSlots; $numSlots > 0; $numSlots--, $startSlotIdx++) {

          $startSlotIdx = $this->getNextRealTimeSlotIdx($startSlotIdx);

          if (    isset($this->startTimes[$startSlotIdx])
               && $this->startTimes[$startSlotIdx]['real']) { // valid timeslot

              $out[] = ['s' => $this->asHHMMSS($this->startTimes[$startSlotIdx]['s']),
                        'e' => $this->asHHMMSS($this->startTimes[$startSlotIdx]['e'])];
          }
      }      
      $this->outSlots = $out;
      return $out;
  }

  /**
   * find required timeslot using a nodified binary search on $startTimes 
   *      
   * This can be used to find the next valid timeslot so we need to return 
   * various conditions:
   * 
   *  o  -1           -- timeNow is before the first valid timeslot
   *  o  0 .. n       -- timeslot (real or not) that is within the array
   *  o  PHP_MAX_INT  -- timeNow is after the end of the array         
   *      
   * @param string   current time   
   * @param integer  startRange  to  timeslots to search  
   * @param integer  endRange  of timeslots  to search
   * @return integer index 
   */ 
  protected function searchStartTimes($timeNow, $rangeStart, $rangeEnd) {  

//      \Kint::dump(__METHOD__.__LINE__, $timeNow, $this->asHHMMSS($timeNow), $rangeStart, $rangeEnd);

      while ($rangeStart <= $rangeEnd) { 

          // mid point of the range
          $currentIdx = (int) ($rangeStart + ($rangeEnd - $rangeStart) / 2); // see floor()

          if ($timeNow >= $this->startTimes[$currentIdx]['s']) { // possible start key

              // check is within the end of the timeSlot
              if ($timeNow <= $this->startTimes[$currentIdx]['e']) { // found it
                  return $currentIdx; // finished
              }   

              // not found correct time slot yet - search upper range
              if ($timeNow >= $this->startTimes[$currentIdx]['s']) {
                  $rangeStart = $currentIdx + 1;                  
              }

          } else {
            // timeNow is after current StartTime  - go find a lower range
              $rangeEnd = $currentIdx - 1;                            
          } 
      } // endwhile

      return $rangeEnd < 0 ? -1 : PHP_INT_MAX; // not in the array
  }

  /**
   * Find the next 'real' timeSlot in the array
   * 
   *  The input can be: 
   *     o Before the first time in the array
   *     o On a timeSlot in the array
   *     o On a 'gap' in the array 
   *
   *  PHP_INT_MAX indicates not in the array.   
   * 
   * @param  integer Current timeslot position 
   * @return integer    
   */
  protected function getNextRealTimeSlotIdx($startSlotIdx) {

      while (    $startSlotIdx < 0  
             || ( isset($this->startTimes[$startSlotIdx])
                  && !$this->startTimes[$startSlotIdx]['real'])) {

          $startSlotIdx++;       
      }

      if (!isset($this->startTimes[$startSlotIdx])) {
          $startSlotIdx = PHP_INT_MAX;
      }

      return $startSlotIdx;
  }

  /**
   *  get any information from the class. It is maintained correctly
   */     
  public function __get($name) {
     if (property_exists($this, $name)) {
        return $this->$name;
     }
     return null;
  }

  public function asSeconds($hhmmss) {
      return strtotime($hhmmss);
  }

  public function asHHMMSS($seconds) {
      $this->dateWhen->setTimestamp($seconds);
      return $this->dateWhen->format('H:i:s');
  }

} // end class

Test Data and Lookup a number of different 'timeNow'

Input real timeslots:

$timeSlots = Array (
    "12:00:00" => "12:05:00",
    "12:10:00" => "12:15:00",
    "16:40:00" => "16:45:00",
    "16:50:00" => "17:00:00"
);

Sample 'timeNow' list:

 $testData = ['11:59:00', '12:01:00', '15:00:00', '16:51:00', '17:01:00'];

Create the class and execute the lookups:

$timeRanges = new TimeRanges($timeSlots);

// run the search
$timeRanges = new TimeRanges($timeSlots);

$foundSlots = array();
foreach ($testData as $timeNow) { // process all the test data times...
    $foundSlots[] = $timeRanges->findTimeSlots($timeNow);
}

Output Results

testTime: 11:59:00
Array
(
    [0] => Array
        (
            [s] => 12:00:00
            [e] => 12:05:00
        )
)


testTime: 12:01:00
Array
(
    [0] => Array
        (
            [s] => 12:00:00
            [e] => 12:05:00
        )
    [1] => Array
        (
            [s] => 12:10:00
            [e] => 12:15:00
        )
)

testTime: 15:00:00
Array
(
    [0] => Array
        (
            [s] => 16:40:00
            [e] => 16:45:00
        )
)

testTime: 16:51:00
Array
(
    [0] => Array
        (
            [s] => 16:50:00
            [e] => 17:00:00
        )
)

testTime: 17:01:00
Array
(
)

Answer 2

Hope you are looking for something like below:

<?php
$timeSlots = Array (
  "12:00:00" => "12:05:00",
  "12:10:00" => "12:15:00",
  "16:40:00" => "16:45:00",
  "16:50:00" => "17:00:00"
);

function getTimeSlots ($timeSlots,$currentTime) {

 $new_time_slot = [];
 array_walk($timeSlots,function($end,$start) use($currentTime,&$new_time_slot){
    if($currentTime<=strtotime($start)){
        $new_time_slot[$start] = $end;
    }
});

  return $new_time_slot;
}

$currentTime = strtotime("12:14:00"); // or time() to get current time

$new_time_slot = getTimeSlots($timeSlots,$currentTime);

print_r($new_time_slot);