合并区间

  • Z时代
  • 2024-01-10
  • 分类：综合

编程

给出一个区间的集合，请合并所有重叠的区间。
示例 1:
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

代码

<?php
/**
 * @description 对一个二维数组进行合并，如元素中存在重叠，则将元素进行合并
 * @param $multiIntevalArr array 待合并的二维数组，每一个元素有两个(原则上)从小到大已排好序的数值型值
 * @return array 合并好的二维数组
 **/
function multiIntevalMerge($multiIntevalArr) 
{
    //边界判断
    if (!is_array($multiIntevalArr)) {
        return $data;
    }
    if (count($multiIntevalArr) <= 1) {
        return $multiIntevalArr;
    }
    //左起点排序
    $toSortArr = $newArr = [];
    foreach ($multiIntevalArr as $key => $value) {
        //对元素进行校验
        if (!is_array($value) || count($value) != 2) {
            return $multiIntevalArr;
        }
        //为提高代码健壮性，这里对元素内部未排好序的元素再判断一次，也扩大了此方法的适用范围
        if ($value[0] > $value[1]) {
            $multiIntevalArr[$key][0] = $value[1];
            $multiIntevalArr[$key][1] = $value[0];
        }
        $leftStart = $multiIntevalArr[$key][0];
		//重复左起点判断，如果已存在，则选取右边更大的元素
		if (isset($toSortArr[$leftStart])) {
		    $previousRightValue = $multiIntevalArr[$toSortArr[$leftStart]][1];
			$newRightValue = $multiIntevalArr[$key][1];
			if ($newRightValue > $previousRightValue) {
			    $toSortArr[$leftStart] = $key;
			}
		} else {
		    $toSortArr[$leftStart] = $key;
		}
    }
    ksort($toSortArr);
    foreach ($toSortArr as $originalKey) {
		$newArr[] = $multiIntevalArr[$originalKey];
    }
    //遍历，合并
    $i = count($newArr)-1;
    while ($i>0) {
        $rightItem = $newArr[$i];
        $leftItem = $newArr[$i-1];
        if ($rightItem[0] <= $leftItem[1]) {
            $newArr[$i-1] = [$leftItem[0], $rightItem[1]];
            unset($newArr[$i]);
		}
		$i--;
    }
    return array_values($newArr);
}

输入

//注意：这里既有左起点重复的情况，也有元素内部未排好序的情况
$multiIntevalArr = [[6, 1], [1,3], [11,7], [8,10], [15,18]];
$res = multiIntevalMerge($multiIntevalArr);
var_dump($res);

输出

array(3) {
 [0]=>
 array(2) {
   [0]=>
   int(1)
   [1]=>
   int(6)
 }
 [1]=>
 array(2) {
   [0]=>
   int(7)
   [1]=>
   int(10)
 }
 [2]=>
 array(2) {
   [0]=>
   int(15)
   [1]=>
   int(18)
 }
}

时间复杂度: O(n)

思考: 应该有更好的排序方法。

以上是 合并区间 的全部内容， 来源链接： utcz.com/z/515959.html

回到顶部