在PHP数组中合并重叠的范围？

Question

我有一个以下格式的数组：

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

每个项都是一个X到Y的范围。我想将数组中重叠的范围合并，得到更像这样的结果：

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

如何最好地完成这个任务？

- Frxstrem

Answer 1

虽然未经测试，但这里的想法是先按第一个元素对数据进行排序，然后尽可能地将后续元素与前一个元素合并。

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

- Matthew

---

+1 这是最干净、最高效的O(n)算法。这正是我心中所想的算法，你比我先实现了它。 - Benbob

+1 在 @ $data[$n][1] 中有什么作用？当使用浮点数时，这在我的情况下不起作用。 - Tom

@Tom，对于整数，您希望将[1,2]，[3,4]视为一个单一的范围[1,4]。在这种情况下，它应该是这样写的：如果(3 > 2 + 1)，则开始一个新的范围。对于浮点数，这并不是非常有用。可以删除或将+1设置为非常小的增量（+.00001），具体取决于您认为的足够小的数字大小。 - Matthew

这个 O(n) 是怎么来的？一开始的排序已经是 nlogn 了。 - Pwnna

你是一个邪恶的天才！！虽然我正在处理日期（除了第二个if()块之外，到处都要使用strtotime()），但你为我节省了一些CPU和几行代码，并在第一个if()块中添加了60（即60秒）而不是1。如果有更好的合并日期时间范围的方法，我很想看到（作为更新）（尽管我还没有绝望到发表新问题）。 - Fr0zenFyr

这是O(n * log(n))。 - BMiner

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

- Mark Baker

---

这个方法应该可以工作，但是在处理大范围时会变得非常缓慢。 - Matthew

Answer 3

好的，我起草了这个，所以可能有些小问题。使用下面看到的数据进行测试，似乎工作得很好。可能不是最好的方法，但它是一种方法，而且确实有效。如果有问题，请让我知道。

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

输出：

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

希望它对你有用！

编辑：

看来我被一个小时击败了 =\ 哦，算了！我还是发表一下，因为这是一种不同的方法，尽管我可能会选择konforce的方法。

- Jim