Combining overlapping periods?

Question

PHP

Good afternoon.
Help with logic.
It is necessary to combine the periods that intersect.
We have for example 5 time intervals (\DateTime):
For simplicity, an array hung.
start - period start date
end - period end date

[
    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'
    ],
]

How to run them in cycles, so that at the output we get an array where the intersecting periods were separate?
Those. something like this:

[
    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'
        ]
    ]
]

Then I will finish what would be 01/01/2017 - 01/20/2017 ...

Answer 1

First, I would convert the dates to a format that is easy to compare:

spoiler

$intervals = 
  ;

Then we need a function that determines the intersection of the intervals and a function that combines the intervals with the addition of subintervals:

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']));
}

Now we write a function that once checks all intervals for intersections:

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;
}

And finally, a loop that combines intervals:

spoiler

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

We launch:

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
        )
)