Merging overlapping ranges in PHP arrays?

Question

I have an array in the following format:

array(
  0 => array(1, 5),
  1 => array(4, 8),
  2 => array(19, 24),
  3 => array(6, 9),
  4 => array(11, 17),
);

Where each item is a X-to-Y range. What I would like to merge the overlapping ranges in the array, to get something more like this:

array(
  0 => array(1, 9), // 1-5, 4-8 and 6-9 are overlapping, so they are merged
  1 => array(11, 17),
  2 => array(19, 24),
);

What would be the best way to accomplish this?

Answer 1

Untested, but the idea here is to sort the data first by the first element, then merge subsequent elements with the previous one as long as possible.

usort($data, function($a, $b)
{
        return $a[0] - $b[0];
});

$n = 0; $len = count($data);
for ($i = 1; $i < $len; ++$i)
{
        if ($data[$i][0] > $data[$n][1] + 1)
                $n = $i;
        else
        {
                if ($data[$n][1] < $data[$i][1])
                        $data[$n][1] = $data[$i][1];
                unset($data[$i]);
        }
}

$data = array_values($data);

Answer 2

$input = array( 0 => array(1, 5),
                1 => array(4, 8),
                2 => array(19, 24),
                3 => array(6, 9),
                4 => array(11, 17),
              );


$tmpArray = array();
foreach($input as $rangeSet) {
    $tmpArray = array_unique(array_merge($tmpArray,range($rangeSet[0],$rangeSet[1])));
}


sort($tmpArray);

$oldElement = array_shift($tmpArray);
$newArray = array(array($oldElement));
$ni = 0;
foreach($tmpArray as $newElement) {
    if ($newElement > $oldElement+1) {
        $newArray[$ni++][] = $oldElement;
        $newArray[$ni][] = $newElement;
    }
    $oldElement = $newElement;
}
$newArray[$ni++][] = $oldElement;

var_dump($newArray);