Generate unique non-overlapping ranges from list of ranges in PHP?

Question

Algorithm question which I seem to be having trouble wrapping my head around today if someone can point me in the right direction. It feels like something which should already be solved that I could lookup but I am having difficulty finding it.

I have some ranges and I want to get new unique non-overlapping ranges from these. For example:

My ranges

[
  [0] => [
           'Min' => 5,
           'Max' => 10
         ],
  [1] => [
           'Min' => 5,
           'Max' => 12
         ],
  [2] => [
           'Min' => 13,
           'Max' => 15
         ],
  [3] => [
           'Min' => 13,
           'Max' => 18
         ],
  [4] => [
           'Min' => 20,
           'Max' => 24
         ],
]

What I would like out is:

Note keys 2 and 4 have changed different fixing the overlapping issue.

[
  [0] => [
           'Min' => 5,
           'Max' => 10
         ],
  [1] => [
           'Min' => 11,
           'Max' => 12
         ],
  [2] => [
           'Min' => 13,
           'Max' => 15
         ],
  [3] => [
           'Min' => 16,
           'Max' => 18
         ],
  [4] => [
           'Min' => 20,
           'Max' => 24
         ],
]

Note how 19 is not there as its not a number within any of the original ranges.

I've tried searching but can't seem to think of what this kind of algorithm would be named so I am getting lots of irrelevant results.

Also notes how non of the ranges at the end overlap and contain the numbers unique (either in a min or max).

Thanks,

Answer 1

This is how I would go about:

1. Order the array entries with usort. First by Min ascending, then by Max descending.
2. Initialize $upperLimit with 0.
3. Then, loop over the array and
   1. Set Min to max($upperLimit + 1, ['Min'])
   2. If Min is >= Max, throw away this entry
   3. Set $upperLimit to max($upperLimit, ['Max'])