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

Alright, drafted this up, so it may have quirks. Tested it with the data seen below and seemed to work just fine. May not be the best way to do it, but it is one way and it does work. Questions let me know.

function combineRange($array) {
    if (is_array($array)) {
        // Sort the array for numerical order
        sort($array);

        // Set Defaults
        $prev = array();
        $prev_key = null;

        foreach ($array as $key => $item) {
            // First time around setup default data
            if (empty($prev)) {
                $prev = $item;
                $prev_key = $key;
                continue;
            }

            if ($item[0] >= $prev[0] && $item[0] <= $prev[1]) {
                // Incase the last number was less than do not update
                if ($array[$prev_key][1] < $item[1])
                    $array[$prev_key][1] = $item[1];

                unset($array[$key]);
            }else {
                $prev_key = $key;
            }       

            $prev = $item;
        }
    }

    return $array;
}

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

var_dump(combineRange($array));

Outputs:

array(3) {
  [0]=>
  array(2) {
    [0]=>
    int(1)
    [1]=>
    int(9)
  }
  [3]=>
  array(2) {
    [0]=>
    int(11)
    [1]=>
    int(17)
  }
  [5]=>
  array(2) {
    [0]=>
    int(19)
    [1]=>
    int(30)
  }
}

Hope it works for ya!

EDIT

I see I was beaten out by an hour =\ Oh well! I am still posting as it is a different method, granted I would probably choose konforce's method instead.

Answer 2

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 3

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