PHP Получить периоды работоспособных из массива перекрывающихся инцидентов

Question

Решение:

Я смотрел на это: Merging overlapping ranges in PHP arrays?

и решить мою проблему в этом примере: https://3v4l.org/XCtlT

нерабочего код пример: https://3v4l.org/sStTT

По сути, у меня есть массив перекрывающихся простоев инцидентов, выглядит следующим образом:

$incidents = [ 
    ['start' => '2016-01-05 00:00:00', 'end' => '2016-01-10 23:59:59'], 
    ['start' => '2016-01-07 00:00:00', 'end' => '2016-01-15 23:59:59'], // overlapping 
    ['start' => '2016-01-12 00:00:00', 'end' => '2016-01-13 23:59:59'], // overlapping 
    ['start' => '2016-01-20 00:00:00', 'end' => '2016-01-25 23:59:59'], 
    ['start' => '2016-01-23 00:00:00', 'end' => '2016-01-24 23:59:59'] // overlapping 
]; 

И от инцидентов массива я ожидал, чтобы получить результат ниже как массив безотказной работы.

Array 
(
    [0] => Array 
     (
      [start] => 2016-01-01 00:00:00 
      [end] => 2016-01-05 00:00:00 
     ) 

    [1] => Array 
     (
      [start] => 2016-01-15 23:59:59 
      [end] => 2016-01-20 00:00:00 
     ) 

    [2] => Array 
     (
      [start] => 2016-01-25 23:59:59 
      [end] => 2016-01-31 23:59:59 
     ) 
) 

К сожалению, моя логическая игра недостаточно хороша, чтобы выполнить задачу достаточно надежно и эффективно. В реальном примере у меня около 2,5 миллионов строк инцидентов в БД.

Что вы думаете об использовании 2 для циклов для расчета времени безотказной работы?

Есть ли более эффективные/более простые способы сделать это?

Можете ли вы завершить логику, чтобы результат работы работал по назначению?

Answer 1

Есть четыре шага алгоритма, как это:

1. Фильтр инцидентов на те, которые перекрывались свой отчет диапазон дат
2. Сортировка инцидентов по инциденту начинают
3. Объединить все инциденты в смежных блоках (O(n) операции)
4. Invert этих диапазоны, возвращая промежутки между слившимися инцидентами (O(n) операции)

Шаги 1 и 2 могут быть просто обработаны в запросе к базе данных, таких как:

select start, end 
from  incidents 
where  start < :reportEnd and 
      end > :reportStart 
order by start