العثور على جميع التباديل داخل صفيف PHP المتداخل
-
08-07-2019 - |
سؤال
بالنظر إلى مجموعة العينات التالية، كيف يمكنني العثور على كافة التباديل للأوقات المتاحة بحيث يتم استيفاء المبلغ المطلوب؟وبعبارة أخرى، يجب أن تنتج مجموعة المتابعة ما يلي:
متاح بتاريخ 14-05-2008 من الساعة 08:00 إلى 08:10 باستخدام المصدر 10 و13
متاح بتاريخ 14-05-2008 من الساعة 08:10 إلى 08:20 باستخدام المصدر 10 و13
print("Array(
[amountNeeded] => 2
[resources] => Array
(
[0] => Array
(
[resourceID] => 10
[blocks] => Array
(
[0] => Array
(
[availDate] => 2008-05-14
[startTime] => 08:00
[endTime] => 08:10
)
[1] => Array
(
[availDate] => 2008-05-14
[startTime] => 08:10
[endTime] => 08:20
)
[2] => Array
(
[availDate] => 2008-05-14
[startTime] => 08:20
[endTime] => 08:30
)
...
[1] => Array
(
[resourceID] => 13
[blocks] => Array
(
[0] => Array
(
[availDate] => 2008-05-14
[startTime] => 08:00
[endTime] => 08:10
)
[1] => Array
(
[availDate] => 2008-05-14
[startTime] => 08:10
[endTime] => 08:20
)
[2] => Array
(
[availDate] => 2008-05-14
[startTime] => 08:30
[endTime] => 08:40
)
...
");
المحلول
ما تبحث عنه ليس له علاقة بالتباديل.أنت تفكر في تداخل الفترات الزمنية، وأرى نهجين:
- قم بالمعالجة المسبقة لجميع فتراتك الزمنية في مخطط زمني، ثم استعلم عن المخطط الزمني، أو
- قم بمسح جميع كتل الموارد الخاصة بك بالتوازي.
يتطلب الخيار الأول مساحة أكبر من الذاكرة ولكنه أسهل في الفهم؛والثاني قد يكون أقل تعطشًا للموارد ولكنه أكثر تعقيدًا في البرمجة.وسيستفيد كلاهما من تقليل مجموعة البيانات التي سيتم أخذها في الاعتبار، أي تحديد الفترة الزمنية المستهدفة.
الخيار رقم 1 هو كما يلي (تم تنفيذه في OO PHP5):
<?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}"
);
}
}
?>
نصائح أخرى
وانه دعا التباديل، بكلمة غرامة. إلقاء نظرة على هذا بلوق وظيفة ، لتنفيذ عام.