Объединение пересекающихся периодов?

Question

[Алекс]

Добрый день.
Помогите с логикой.
Надо объединить периоды, которые пересекаются.

Имеем к примеру 5 временных отрезков (\DateTime):

Для простоты, нависал массив.
start - дата начала периода
end - дата окончания периода

[
    0 => [
        'start' => '01.01.2017', 
        'end'   => '06.01.2017'
    ],
    1 => [
        'start' => '21.01.2017', 
        'end'   => '30.01.2017'
    ],
    2 => [
        'start' => '10.01.2017', 
        'end'   => '20.01.2017'
    ],
    3 => [
        'start' => '05.01.2017', 
        'end'   => '16.01.2017'
    ],
    4 => [
        'start' => '15.01.2017', 
        'end'   => '20.01.2017'
    ],
]

Как их прогнать в циклах, что бы на выходе получить массив где пересекающиеся периоды были отдельно?
Т.е. как то так:

[
    0 => [
      // для будущего объединения в один период
        0 => [
            'start' => '01.01.2017', 
            'end'   => '06.01.2017'
        ],
        1 => [
            'start' => '10.01.2017', 
            'end'   => '20.01.2017'
        ],
        2 => [
            'start' => '05.01.2017', 
            'end'   => '16.01.2017'
        ],
        3 => [
            'start' => '15.01.2017', 
            'end'   => '20.01.2017'
        ]
    ]
    // период который не пересекается
    1 => [
        0 => [
            'start' => '21.01.2017', 
            'end'   => '30.01.2017'
        ]
    ]
]

Потом доделаю что бы было 01.01.2017 - 20.01.2017 ...

Answer 1

[Rsa97]

Для начала, я бы преобразовал даты в формат, удобный для сравнения:

spoiler

$intervals = 
  [['start' => '2017-01-01', 'end'   => '2017-01-06'],
   ['start' => '2017-01-21', 'end'   => '2017-01-30'],
   ['start' => '2017-01-10', 'end'   => '2017-01-20'],
   ['start' => '2017-01-05', 'end'   => '2017-01-16'],
   ['start' => '2017-01-15', 'end'   => '2017-01-20']];

Затем нужна функция, определяющая пересечение интервалов и функция, объединяющая интервалы с добавлением подинтервалов:

spoiler

function is_intersect($int1, $int2) {
  return ($int2['end'] >= $int1['start'] && $int1['end'] >= $int2['start']);
}
function combine($int1, $int2) {
  if (!isset($int1['subintervals'])) {
      $int1['subintervals'] = [$int1];
  }
  if (!isset($int2['subintervals'])) {
      $int2['subintervals'] = [$int2];
  }
  return array('start' => min($int1['start'], $int2['start']), 'end' => max($int1['end'], $int2['end']),
               'subintervals' => array_merge($int1['subintervals'], $int2['subintervals']));
}

Теперь пишем функцию, один раз проверяющую все интервалы на пересечения:

spoiler

function combine_intersected($intervals) {
  $result = [];
  $noIntersects = true;
  foreach ($intervals as $int1) {
    $combined = false;
    foreach ($result as &$int2) {
      if (is_intersect($int1, $int2)) {
        $int2 = combine($int1, $int2);
        $noIntersects = false;
        $combined = true;
        break;
      }
    }
    if (!$combined) {
      $result[] = $int1;
    }
  }
  if ($noIntersects) {
    return false;
  }
  return $result;
}

Ну и, напоследок, цикл, объединяющий интервалы:

spoiler

while ($ints = combine_intersected($intervals)) {
  $intervals = $ints;
}

Запускаем:

spoiler

Array (
    [0] => Array (
            [start] => 2017-01-01
            [end] => 2017-01-20
            [subintervals] => Array (
                    [0] => Array (
                            [start] => 2017-01-10
                            [end] => 2017-01-20
                        )
                    [1] => Array (
                            [start] => 2017-01-15
                            [end] => 2017-01-20
                        )
                    [2] => Array (
                            [start] => 2017-01-05
                            [end] => 2017-01-16
                        )
                    [3] => Array (
                            [start] => 2017-01-01
                            [end] => 2017-01-06
                        )
                )
        )
    [1] => Array (
            [start] => 2017-01-21
            [end] => 2017-01-30
        )
)

Comments

[Алекс]

Спасибо.
Вы предоставили объемный код.
Но я просил просто о логике. Реализацию все равно оставляю за собой.
Даты, приведены как пример, на самом деле там гигантские объекты с десятками уровней.
Собственно это я указал. Приводить DateTime к строке, уже как минимум не серьезно.

[Rsa97]

Алекс: Ну, приводить к строке не обязательно, даже код не поменяется. Единственное, о чём я не подумал сразу - если предварительно отсортировать массив по start, то всё выполнится за один проход.

Answer 2

[Mercury13]

отсортировать массив по start
текКонец := −∞   // или, например, ⌀ или 0000-01-01
текИндекс := −1
для v : массив
  если v.start > текКонец
    текИндекс += 1
  результат[текИндекс].приклеить(v)
  текКонец := макс(текКонец, v.end)

Если же нужно объединять прямо на ходу…

отсортировать массив по start
текКонец := −∞   // или, например, ⌀ или 0000-01-01
текИндекс := −1
для v : массив
  если v.start > текКонец
    текИндекс += 1
    результат[текИндекс] := v
  иначе
    результат[текИндекс] := объединить(результат[текИндекс], v)
  текКонец := макс(текКонец, v.end)

Разумеется, я тут опустил вопросы, связанные с датами-строками и их сравнением. Но вам их придётся решить.
Изначально считается, что везде end > start. Если не так — данные некорректные и с этим придётся что-то делать.
Также считается, что массив «результат» ассоциативный (как в PHP).

Comments

[Алекс]

Логику я понял, спасибо.
Постараюсь реализовать всю эту котовасию.
Массив указал просто для наглядности, на самом деле там большие объекты.

Answer 3

[Boris Köln]

function isOverlapped($dateRange1, $dateRange2)
    {
        return (
            $dateRange1['start'] >= $dateRange2['start']
            && $dateRange1['start'] <= $dateRange2['end']
            
            ||

            $dateRange1['end'] >= $dateRange2['start']
            && $dateRange1['end'] <= $dateRange2['end']
        );
    }

stard/end должны быть сравниваемые! Либо DateTime, либо timestamp, либо строка Ymd, но не dmY.

Как вызвать эту функцию для каждой пары дат - домашнее задание сделайте самостоятельно.

Comments

[Алекс]

Спасибо.
Я указал что DateTime, массив написал для наглядности.