sensus
@sensus

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

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

Имеем к примеру 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 ...
  • Вопрос задан
  • 1997 просмотров
Решения вопроса 3
Rsa97
@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
        )
)
Ответ написан
@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).
Ответ написан
@BorisKorobkov Куратор тега PHP
Web developer
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.

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
28 мар. 2024, в 18:16
1000 руб./за проект
28 мар. 2024, в 18:15
90000 руб./за проект
28 мар. 2024, в 18:05
5000 руб./за проект