Комбинации диапазонов дат, охватывающих все дни диапазона дат ввода

Question

Я хочу найти все возможные комбинации диапазонов дат, которые перекрывают диапазон дат ввода. Например, если пользовательский ввод 2013/01/10 в 2013/01/25, и я ниже диапазонов дат:

2013/01/08 to 2013/01/10 
2013/01/09 to 2013/01/15 
2013/01/10 to 2013/01/20 
2013/01/18 to 2013/01/27 
2013/01/14 to 2013/01/19 
2013/01/19 to 2013/01/25 
2013/01/14 to 2013/01/26 
2013/01/10 to 2013/01/26 

Я хочу, чтобы найти все возможные комбинации указанных выше дат, которая перекрывается даты ввода (2013/01/10 до 2013/01/25).

два примера диапазона дат, который перекрывается даты ввода является:

{2013/01/09 to 2013/01/15, 2013/01/14 to 2013/01/26} 
{2013/01/09 to 2013/01/15, 2013/01/14 to 2013/01/19, 2013/01/19 to 2013/01/25} 

Я не перечислены все возможные диапазоны дат, которые перекрывает диапазон дат ввода!
Я хочу найти комбинацию диапазонов дат, охватывающих все дни диапазона дат ввода !, Если вы посмотрите на два примера, я объединил диапазоны дат, охватывая все дни ввода даты!
Я не хочу проверять одну дату с диапазоном дат ввода, чтобы найти, что если диапазон дат охватывает все дни ввода даты или нет !, я хочу комбинировать диапазоны дат, чтобы найти все возможные комбинации диапазонов дат, которые охватывают все дней с диапазоном дат ввода.
Я хочу алгоритм поиска всех возможных комбинаций дат, который охватывает все дни диапазона входных дат. Есть ли быстрый алгоритм, который решает эту проблему?

Answer 1

Я добавил еще пару элементов данных, чтобы сделать его более интересным:

$start = strtotime('2013/01/10'); 
$end = strtotime('2013/01/25'); 
$range[0]['start'] = "2013/01/08"; 
$range[0]['end'] = "2013/01/10"; 
$range[1]['start'] = "2013/01/09"; 
$range[1]['end'] = "2013/01/15"; 
$range[2]['start'] = "2013/01/10"; 
$range[2]['end'] = "2013/01/20"; 
$range[3]['start'] = "2013/01/18"; 
$range[3]['end'] = "2013/01/27"; 
$range[4]['start'] = "2013/01/14"; 
$range[4]['end'] = "2013/01/19"; 
$range[5]['start'] = "2013/01/19"; 
$range[5]['end'] = "2013/01/25"; 
$range[6]['start'] = "2013/01/14"; 
$range[6]['end'] = "2013/01/26"; 
$range[7]['start'] = "2013/01/10"; 
$range[7]['end'] = "2013/01/26"; 
$range[8]['start'] = "2013/01/9"; 
$range[8]['end'] = "2013/01/15"; 
$range[9]['start'] = "2013/01/13"; 
$range[9]['end'] = "2013/01/19"; 
$heads = array(); 
$tails = array(); 
$combos = array(); 
$h = 0; 
foreach ($range as $key => $value){ 
    $r1 = strtotime($value['start']); 
    $r2 = strtotime($value['end']); 
    if ($r1 <= $start && $r2 >= $end){ 
     $combos[] = $key; 
    } elseif($r1 <= $start && $r2 > $start) { 
     $heads[$h]['r1'] = $r1; 
     $heads[$h]['r2'] = $r2; 
     $heads[$h]['seq'] = $key; 
     $h++; 
    } elseif($r1 > $start && $r1 < $end && $r1 < $r2) { 
     $tails[$key]['r1'] = $r1; 
     $tails[$key]['r2'] = $r2; 
     $tails[$key]['seq'] = $key; 
    } 
} 
while (count($tails) > 0){ 
    $heads2 = array(); 
    $tails2 = array(); 
    $h2 = 0; 
    foreach ($heads as $key1 => $value1){ 
     foreach ($tails as $key2 => $value2){ 
      if (($value1['r1'] < $value2['r1']) && ($value1['r2'] >= $value2['r1']) && ($value1['r2'] < $value2['r2'])){ 
       $seq = $value1['seq'].':'.$value2['seq']; 
       //keep tail alive, but don't change key 
       $tails2[$key2]['r1'] = $value2['r1']; 
       $tails2[$key2]['r2'] = $value2['r2']; 
       $tails2[$key2]['seq'] = $key2; 
       if ($value2['r2'] >= $end){ 
        $combos[] = $seq; 
       } else { 
        $heads2[$h2]['r1'] = $value1['r2']; 
        $heads2[$h2]['r2'] = $value2['r2']; 
        $heads2[$h2]['seq'] = $seq; 
        $h2++; 
       } 
      } 
     } 
    } 
    $heads = $heads2; 
    $tails = $tails2; 
} 

Массив $combos содержит последовательность ключей массива, разделенных двоеточием, ссылающихся ключи массива исходного массива. Вот возможный способ вывода изображения:

$html = ''; 
foreach ($combos as $key => $value){ 
    $p = '<p>'; 
    $seqs = explode(':', $value); 
    foreach ($seqs as $key2 => $value2){ 
     $p .= $range[$value2]['start'].' - '.$range[$value2]['end'].'; '; 
    } 
    $html .= substr($p, 0, -2).'</p>'; 
} 
echo $html; 

Это отображает следующее:

2013/01/10 - 2013/01/26 
2013/01/09 - 2013/01/15; 2013/01/14 - 2013/01/26 
2013/01/10 - 2013/01/20; 2013/01/18 - 2013/01/27 
2013/01/10 - 2013/01/20; 2013/01/19 - 2013/01/25 
2013/01/10 - 2013/01/20; 2013/01/14 - 2013/01/26 
2013/01/9 - 2013/01/15; 2013/01/14 - 2013/01/26 
2013/01/09 - 2013/01/15; 2013/01/14 - 2013/01/19; 2013/01/18 - 2013/01/27 
2013/01/09 - 2013/01/15; 2013/01/14 - 2013/01/19; 2013/01/19 - 2013/01/25 
2013/01/09 - 2013/01/15; 2013/01/13 - 2013/01/19; 2013/01/18 - 2013/01/27 
2013/01/09 - 2013/01/15; 2013/01/13 - 2013/01/19; 2013/01/19 - 2013/01/25 
2013/01/9 - 2013/01/15; 2013/01/14 - 2013/01/19; 2013/01/18 - 2013/01/27 
2013/01/9 - 2013/01/15; 2013/01/14 - 2013/01/19; 2013/01/19 - 2013/01/25 
2013/01/9 - 2013/01/15; 2013/01/13 - 2013/01/19; 2013/01/18 - 2013/01/27 
2013/01/9 - 2013/01/15; 2013/01/13 - 2013/01/19; 2013/01/19 - 2013/01/25 

Answer 2

я не совсем уверен, почему 2013-01-09 to 2013-01-15 отсутствует в списке, если вы можете найти 2013-01-09 to 2013-01-15, но вы можете изменить этот класс ниже по желанию

$range = [ 
     new DateManager("2013/01/08", "2013/01/10"), 
     new DateManager("2013/01/09", "2013/01/15"), 
     new DateManager("2013/01/10", "2013/01/20"), 
     new DateManager("2013/01/18", "2013/01/27"), 
     new DateManager("2013/01/14", "2013/01/19"), 
     new DateManager("2013/01/19", "2013/01/25"), 
     new DateManager("2013/01/14", "2013/01/26"), 
     new DateManager("2013/01/10", "2013/01/26") 
]; 

$find = new DateManager("2013/01/10", "2013/01/25"); 

foreach($range as $date) { 
    $find->overlap($date) && print($date->getRange() . PHP_EOL); 
} 

Выход

2013/01/09 to 2013/01/15 
2013/01/10 to 2013/01/20 
2013/01/14 to 2013/01/19 
2013/01/19 to 2013/01/25 

Класс

class DateManager { 
    private $start, $end; 

    function __construct($start, $end, $format = "Y/m/d") { 
     $this->start = $start instanceof DateTime ? $start : DateTime::createFromFormat($format, $start); 
     $this->end = $end instanceof DateTime ? $end : DateTime::createFromFormat($format, $end); 
    } 

    function getStart() { 
     return $this->start; 
    } 

    function getEnd() { 
     return $this->end; 
    } 

    function getRange($format = "Y/m/d") { 
     return sprintf("%s to %s ", $this->start->format($format), $this->end->format($format)); 
    } 

    function between(DateManager $date) { 
     return $date->getStart() >= $this->getStart() && $this->getEnd() <= $date->end; 
    } 

    function overlap(DateManager $date) { 
     return (($date->getStart() >= $this->getStart() || $date->getEnd() > $this->getStart()) && $this->getEnd() >= $date->getEnd()); 
    } 
} 

Answer 3

Преобразовать оба (начало, конец) относится к системному времени (начался на 1/1/70, с шагом = 1s), а после этого - запустить цикл с шагом = 24 * 60 * 60. При необходимости декодируйте каждое значение в печатную форму.