StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>What you are looking for has nothing to do with permutations. You are considering overlapping time periods, and I see two approaches:</p> <ol> <li>Pre-process all your time-periods into a timeline, then query the timeline, or</li> <li>Scan through all your resource-blocks in parallel.</li> </ol> <p>The first option takes more memory but is easier to understand; the second is potentially less resource-hungry but much more complicated to program. Both would benefit from minimizing the dataset to be considered, ie limit the target time period.</p> <p>Option #1 is as follows (implemented in OO PHP5):</p> <pre><code><?php class Resource { protected $name; // resource ID protected $start; // start timestamp protected $finish; // end timestamp // resource available while $start <= current time < $end function __construct($n, $sd, $st, $ed, $et) { $this->name = $n; $this->start = strtotime("$sd $st"); $this->finish = strtotime("$ed $et"); } function getID() { return $this->name; } function getStart() { return $this->start; } function getEnd() { return $this->finish; } } class Timeline { protected $times; // ordered list of start-times; protected $resources; // resources available in each timeslot protected $offs; // iterator offset function __construct() { $this->times = array(); $this->resources = array(); $this->offs = 0; } // binary search, insert if not found, return index private function time_ins($time) { // array is empty? if (count($this->times) == 0) { $this->times[0]= $time; $this->resources[0] = array(); return 0; } $min = $lo = 0; $max = $hi = count($this->times)-1; // binary search while($lo <= $hi) { $mid = ($lo+$hi) >> 1; if ($this->times[$mid] == $time) { // already exists - return index return $mid; } elseif ($this->times[$mid] < $time) { // if value exists, is in upper half of array $lo = $mid+1; if ($lo > $max || $this->times[$lo] > $time) { // $lo points to first value greater than $time // insert new value at $lo array_splice($this->times, $lo, 0, $time); $t = isset($this->resources[$lo-1]) ? $this->resources[$lo-1] : array(); array_splice($this->resources, $lo, 0, $t); return $lo; } } else { // if value exists, is in lower half of array $hi = $mid-1; if ($hi < $min || $this->times[$hi] < $time) { // $hi points to first value less than $time // insert new value at $hi+1 array_splice($this->times, $hi+1, 0, $time); $t = isset($this->resources[$hi+1]) ? $this->resources[$hi+1] : array(); array_splice($this->resources, $hi+1, 0, $t); return $hi+1; } } } } function Add( $start, $end, $id ) { $s = $this->time_ins($start); $e = $this->time_ins($end); for($i = $s; $i < $e; ++$i) $this->resources[$i][]= $id; } function reset() { $offs = 0; } function isValid() { return ($this->offs+1 < count($this->times)); } // omit last time (is end-time only) function next() { $this->offs++; } function resCount() { return count( $this->resources[ $this->offs ] ); } function getStart() { return $this->times[$this->offs]; } function getEnd() { return $this->times[$this->offs + 1]; } function getRes() { return $this->resources[$this->offs]; } } $res = array(); $res[]= new Resource('10', '2008-05-14', '08:00', '2008-05-14', '08:10'); $res[]= new Resource('10', '2008-05-14', '08:10', '2008-05-14', '08:20'); $res[]= new Resource('10', '2008-05-14', '08:20', '2008-05-14', '08:30'); $res[]= new Resource('13', '2008-05-14', '08:00', '2008-05-14', '08:10'); $res[]= new Resource('13', '2008-05-14', '08:10', '2008-05-14', '08:20'); $res[]= new Resource('13', '2008-05-14', '08:30', '2008-05-14', '08:40'); $tl = new Timeline(); foreach($res as $R) $tl->Add( $R->getStart(), $R->getEnd(), $R->getID() ); $needed = 2; $_pre = "\n<p>"; $_post = "</p>"; for( $tl->reset(); $tl->isValid(); $tl->next() ) { $cnt = $tl->resCount(); if ($cnt >= $needed) { $st = date("Y-m-d H:i", $tl->getStart()); $fn = date("Y-m-d H:i", $tl->getEnd()); $res = join(', ', $tl->getRes()); echo ($cnt == $needed ? "{$_pre}Available from $st to $fn using resources ($res){$_post}" : "{$_pre}Available from $st to $fn using any $needed of resources ($res){$_post}" ); } } ?> </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload