题目描述

给定一个无重叠的区间列表 intervals 和一个新的区间 newInterval，将 newInterval 插入到列表中，使得合并后的列表仍然是按照左端点递增顺序排列的，并且重叠的区间被合并成单个区间。

注意：输入类型可以是整数数组，其中每个区间用 [start, end] 表示。

示例

假设我们有以下区间列表和新的区间：

intervals = [[1, 3], [6, 9]]
newInterval = [2, 5]

合并后的区间列表应为：

[[1, 5], [6, 9]]

因为 [2, 5] 与 [1, 3] 重叠，合并后的区间为 [1, 5]。

PHP 示例代码

function insertInterval($intervals, $newInterval) {
    $merged = [];
    $inserted = false;
    
    foreach ($intervals as $interval) {
        if (!$inserted && $newInterval[1] < $interval[0]) {
            // 如果新区间完全在当前区间左侧，则直接添加到结果中
            $merged[] = $newInterval;
            $merged[] = $interval;
            $inserted = true;
        } elseif (!$inserted && $newInterval[0] <= $interval[1]) {
            // 如果新区间与当前区间重叠，合并两个区间
            $newInterval[0] = min($newInterval[0], $interval[0]);
            $newInterval[1] = max($newInterval[1], $interval[1]);
        } elseif ($inserted) {
            // 如果新区间已插入，直接添加当前区间
            $merged[] = $interval;
        }
    }
    
    if (!$inserted) {
        // 如果新区间在所有已知区间之后，直接添加到结果末尾
        $merged[] = $newInterval;
    }
    
    return $merged;
}

// 测试代码
$intervals = [[1, 3], [6, 9]];
$newInterval = [2, 5];
$result = insertInterval($intervals, $newInterval);
print_r($result);

Python 示例代码

def insertInterval(intervals, newInterval):
    merged = []
    inserted = False
    
    for interval in intervals:
        if not inserted and newInterval[1] < interval[0]:
            # 新区间在当前区间左侧
            merged.append(newInterval)
            merged.append(interval)
            inserted = True
        elif not inserted and newInterval[0] <= interval[1]:
            # 新区间与当前区间重叠
            newInterval[0] = min(newInterval[0], interval[0])
            newInterval[1] = max(newInterval[1], interval[1])
        elif inserted:
            # 新区间已插入，添加当前区间
            merged.append(interval)
    
    if not inserted:
        # 新区间在所有区间之后
        merged.append(newInterval)
    
    return merged

# 测试代码
intervals = [[1, 3], [6, 9]]
newInterval = [2, 5]
result = insertInterval(intervals, newInterval)
print(result)

JavaScript 示例代码

function insertInterval(intervals, newInterval) {
    const merged = [];
    let inserted = false;
    
    for (let interval of intervals) {
        if (!inserted && newInterval[1] < interval[0]) {
            // 新区间在当前区间左侧
            merged.push(newInterval);
            merged.push(interval);
            inserted = true;
        } else if (!inserted && newInterval[0] <= interval[1]) {
            // 新区间与当前区间重叠
            newInterval[0] = Math.min(newInterval[0], interval[0]);
            newInterval[1] = Math.max(newInterval[1], interval[1]);
        } else if (inserted) {
            // 新区间已插入，添加当前区间
            merged.push(interval);
        }
    }
    
    if (!inserted) {
        // 新区间在所有区间之后
        merged.push(newInterval);
    }
    
    return merged;
}

// 测试代码
const intervals = [[1, 3], [6, 9]];
const newInterval = [2, 5];
const result = insertInterval(intervals, newInterval);
console.log(result);

在以上示例中，我们遍历了给定的区间列表，并根据新区间的位置进行合并或插入操作。这样，最终得到的 merged 数组就是合并了新区间后的结果。