到目前为止我所拥有的：测试的示例
$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>";
我正在寻求帮助来调整我的当前代码，以便它在$dates数组中循环，选择最早的时间，但这些时间需要能够适应其中的一个和另一个。这需要始终使用已拾取的一个$alreadyChosenDates。在我的示例代码中，我得到了持续时间为300的2016-02-18 02:05:00。
基于上面示例代码的预期结果：
// 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
)
)
另一个开始时间不同的例子：
// 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
)
)
要求
输入：
1( 给定"选定"日期列表2( "候选人"日期列表
输出：1( "无重叠"日期的最终列表
其中：
a( 第一个"选定"数据是"开始"日期即所有候选日期必须在此日期或之后。
b( 日期范围不得重叠。
更新1-提供"设置者和过程"边缘案例
1( 提供setter s：
`setChosen(array $chosenDates)`
`setCandidates(array $candidateDates)`
2( 测试的丢失输入的边缘情况。
3( 通过constructor传递数组是可选的。
更新2-搜索日期范围内的最佳非重叠日期列表
演示：https://eval.in/678371
类源：http://pastebin.com/K81rfytB
- 它通过对给定日期范围内的所有日期进行
brute force搜索来查找列表
todo：将"强力搜索"转换为"动态编程"；通过添加"备忘录化"。这应该不难做到，因为它目前使用的是"决策树"。
我稍后会用有关的说明更新此答案。现在请参阅上面的"演示"链接。
原始答案
演示：
用户提供的数据和中"eval.in"的结果
更新了setters和边缘案例处理
解释(或者我是怎么想的(
如果列表按"开始日期"排序，那么很容易推断日期列表。
a( "所选开始"日期之后的第一个开始日期必须最接近。
我可以立即检测到下一个日期overlaps是否已经选择了。
因此，对列表进行排序是有用的。
为了使检查重叠的代码更容易，我决定将候选日期转换为标准格式，其中包括每个"候选"的"范围"或window作为"epoch秒(unix时间戳("。它使测试更清晰？
输出中不得包含任何重叠的候选日期。
这就是所提供的类的作用。
完成所有工作的类(ScheduleList(
/* ---------------------------------------------------------------------------------
* 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;
}
}
运行它
- 通过传递
chosen数组和"dates"数组来创建ScheduleList的实例 generateList();方法将返回"final"无重叠日期数组
代码：
$datesListGenerator = new ScheduleList($alreadyChosenDates,
$dates);
$final = $datesListGenerator->generateList();
更新：使用setters运行：
$datesListGenerator = new ScheduleList();
$datesListGenerator->setChosen($alreadyChosenDates);
$datesListGenerator->setCandidates($dates);
各种输出
makeDakeRange现在是一个公共函数：
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
最终(与任何候选输入不重叠(
代码：
echo PHP_EOL, PHP_EOL, 'Final List';
foreach ($final as $when) {
$datesListGenerator->displayWhen($when);
}
输出：
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
未使用(在开始或重叠之前(
代码：
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);
}
输出：
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