首页 > 试题广场 >

合并区间

[编程题]合并区间
  • 热度指数:169584 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给出一组区间,请合并所有重叠的区间。
请保证合并后的区间按区间起点升序排列。
//"区间"定义
class Interval {
   int start; //起点
   int end;   //终点
}

数据范围:区间组数 ,区间内 的值都满足
要求:空间复杂度 ,时间复杂度
进阶:空间复杂度 ,时间复杂度
示例1

输入

[[10,30],[20,60],[80,100],[150,180]]

输出

[[10,60],[80,100],[150,180]]
示例2

输入

[[0,10],[10,20]]

输出

[[0,20]]
function merge( $intervals)
{
    // write code here
    $total_intervals = count($intervals);
    $new_intervals = [];
    print_r($new_intervals);
    for($i = 0; $i < $total_intervals; $i++){
        $start = $intervals[$i]->start;
        $end = $intervals[$i]->end;
        for ($j = $i+1; $j < $total_intervals; $j++){
            if($end > $intervals[$j]->start){
                $end = $intervals[$j]->end;
                continue;
            }
            break;
        }
        
        array_push($new_intervals, [$start, $end]);
        $i = $j-1;
    }
    return $new_intervals;
}
发表于 2021-09-26 14:46:53 回复(0)