Как сформировать пересекающиеся периоды?

Question

[Алекс]

Приветствую!
Извиняюсь за обращение, у меня головная боль по работе с датами.
Мне надо сделать следующую вещь: если периоды пересекаются, то надо их разделить.
Входящие данные (для примера, в реальности объекты datetime)

[
    0 => ['openDate' => "2018-05-15", 'closeeDate' => "2018-05-30", "item" => 77],
    1 => ['openDate' => "2018-05-20", 'closeeDate' => "2018-05-25", "item" => 60]
]

В данном примере, первый период надо разделить на два (key: 0, 2).
Т.е. на выходе получить

[
    0 => ['openDate' => "2018-05-15", 'closeeDate' => "2018-05-19", "item" => 77]
    1 => ['openDate' => "2018-05-20", 'closeeDate' => "2018-05-25", "item" => 60],
    2 => ['openDate' => "2018-05-26", 'closeeDate' => "2018-05-30", "item" => 77],
]

Можете подкинуть алгоритм?
Спасибо.

UPD
Разбивать периоды по каждому дню не вариант. Могут прийти десятки массивов, в которых периоды на год или два.
Я пока вижу вариант, искать пересечение (это просто). А как дальше сформировать требуемые периоды. Т.е. подробить.

Answer 1

[Anton Dyrkov]

Насколько я понял получается так

Answer 2

[OKyJIucT]

Каждый диапазон разбить на массив с днями, потом перебирать первый массив и искать значение во втором. Если есть - создавать третий (между первыми двумя) и перенести значение туда, попутно удаляя значение элемента из обоих массивов.

В конце собрать из каждого диапазона массив в исходном формате, используя первый и последний элемент.

Функция для создания массива с датами из диапазона

$from = new \DateTime('2014-01-01');
$to = new \DateTime('2015-11-01');
 
$period = new \DatePeriod($from, new \DateInterval('P1D'), $to);
 
$arrayOfDates = array_map(
    function ($item) {
        return $item->format('Y-m-d');
    },
    iterator_to_array($period)
);

Comments

[Алекс]

К сожалению вариант разбивки по дням не подходит, он слишком трудозатратный.
Могут прийти таких 20 массивов на год или два.
В данном примере я указал совершенно краткий вариант, что бы сильно не заморачиваться.

[OKyJIucT]

Алекс, в чем трудозатраты? Единственное - памяти может потребоваться много, но после обработки каждого массива ее можно очищать с помощью unset. Здесь никаких расчетов сложных нет и выборки из базы тоже. Один массив длиной в полтора года обрабатывается за 0.0045 секунд, не вижу тут особой нагрузки на процессор.

Answer 3

[Александр null]

еще вариант собрать все в один массив

исходные данные
$days = [2018-05-15, 2018-05-30, 2018-05-20, 2018-05-25];
далее сортируем по возрастанию

после чего берем первый элемент и второй -1 день, затем второй и 3-1 день и т.д.

Comments

[Алекс]

Спасибо, такой вариант и я знаю.
Но он не пойдет по совершенно очевидным причинам - даты минимум на год, будут долго обрабатываться.
Ответ не может быть более секунды.

[Владимир Олохтонов]

Алекс, серьезно? Даже питон может делать ~10^6 операций в секунду, сортировка + проход по 365 датам займут меньше 0.03 секунды.

[Алекс]

Владимир Олохтонов, А затем все это пихать в БД, обрабатывать все сотни объектов на каждую дату и тогда ответ пздц будет долгий.
За каждым "item" скрывается сотня объектов, которые тоже несут различные массивы данных.
Т.е. по сути каждый item, это выборка из 63 таблиц и 2х БД проекта booking.com

Прогон обычного массива дат, можно делать на чем угодно и это займет менее секунды.
Но это делается только для тестовых заданиях при приеме джунов.

[Владимир Олохтонов]

Алекс, звучит очень страшно, да. Если у вас проблема с представлением данных, то решать нужно её, а не "разделение периодов".

А где в вашем примере вообще пересечение периодов?