当前位置: 面试刷题>> 插入区间 (经典算法题500道)


题目描述

给定一个无重叠的按升序排列的区间列表 intervals,以及一个新的区间 newInterval,请将 newInterval 插入到列表中,使得合并后的列表仍然是按升序排列且区间无重叠。

示例

示例 1:

输入: intervals = [[1,3],[6,9]], newInterval = [2,5]
输出: [[1,5],[6,9]]

示例 2:

输入: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出: [[1,2],[3,10],[12,16]]
解释: 因为新区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠, 所以将它们合并成一个区间 [3,10].

PHP 示例代码

function insert($intervals, $newInterval) {
    $merged = [];
    $i = 0;
    $n = count($intervals);

    // 将所有小于 newInterval 的区间添加到结果中
    while ($i < $n && $intervals[$i][1] < $newInterval[0]) {
        $merged[] = $intervals[$i++];
    }

    // 合并重叠的区间
    while ($i < $n && $intervals[$i][0] <= $newInterval[1]) {
        $newInterval[0] = min($newInterval[0], $intervals[$i][0]);
        $newInterval[1] = max($newInterval[1], $intervals[$i][1]);
        $i++;
    }

    // 将 newInterval 添加到结果中
    $merged[] = $newInterval;

    // 将剩余区间添加到结果中
    while ($i < $n) {
        $merged[] = $intervals[$i++];
    }

    return $merged;
}

Python 示例代码

def insert(intervals, newInterval):
    merged = []
    i = 0
    n = len(intervals)

    # 插入所有不与 newInterval 重叠的区间
    while i < n and intervals[i][1] < newInterval[0]:
        merged.append(intervals[i])
        i += 1

    # 合并重叠区间
    while i < n and intervals[i][0] <= newInterval[1]:
        newInterval[0] = min(newInterval[0], intervals[i][0])
        newInterval[1] = max(newInterval[1], intervals[i][1])
        i += 1

    # 插入合并后的区间
    merged.append(newInterval)

    # 插入剩余的区间
    while i < n:
        merged.append(intervals[i])
        i += 1

    return merged

JavaScript 示例代码

function insert(intervals, newInterval) {
    const merged = [];
    let i = 0;
    const n = intervals.length;

    // 添加所有小于 newInterval 的区间
    while (i < n && intervals[i][1] < newInterval[0]) {
        merged.push(intervals[i++]);
    }

    // 合并重叠区间
    while (i < n && intervals[i][0] <= newInterval[1]) {
        newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
        newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
        i++;
    }

    // 添加合并后的区间
    merged.push(newInterval);

    // 添加剩余区间
    while (i < n) {
        merged.push(intervals[i++]);
    }

    return merged;
}

码小课网站中有更多相关内容分享给大家学习,涵盖算法、数据结构、编程语言等多个方面,欢迎访问学习!

推荐面试题