力扣经典150题第四十九题：插入区间

用户8589624

发布于 2025-11-13 16:10:47

960

文章被收录于专栏：nginxnginx

题目描述和要求

给定一个无重叠的、按照区间起始端点排序的区间列表 intervals，其中 intervals[i] = [starti, endi] 表示第 i 个区间的开始和结束。同样给定一个区间 newInterval = [start, end] 表示另一个区间的开始和结束。

在 intervals 中插入区间 newInterval，使得 intervals 依然按照 starti 升序排列，且区间之间不重叠（如果有必要的话，可以合并区间）。

返回插入之后的 intervals。

示例解释

示例 1：

输入：intervals = [[1,3],[6,9]], newInterval = [2,5] 输出：[[1,5],[6,9]] 解释：插入新区间 [2,5] 后，原区间 [1,3] 和 [6,9] 合并为 [1,5]。

示例 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]。

解题思路

我们可以对区间进行遍历，根据新区间与当前区间的关系进行合并。具体步骤如下：

初始化一个结果列表，用于存储合并后的区间。
遍历区间列表，如果当前区间的结束位置小于新区间的起始位置，则将当前区间加入结果列表。
如果当前区间的起始位置大于新区间的结束位置，则将新区间加入结果列表，并更新新区间为当前区间。
如果当前区间与新区间存在重叠，则更新新区间的起始位置为当前区间和新区间起始位置的较小值，更新新区间的结束位置为当前区间和新区间结束位置的较大值。
将最后的新区间加入结果列表。
返回结果列表。

算法实现

import java.util.ArrayList;
import java.util.List;

public class InsertInterval {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> merged = new ArrayList<>();
        int index = 0;
        int n = intervals.length;
        
        // 添加所有在新区间之前的区间
        while (index < n && intervals[index][1] < newInterval[0]) {
            merged.add(intervals[index++]);
        }
        
        // 合并重叠的区间
        while (index < n && intervals[index][0] <= newInterval[1]) {
            newInterval[0] = Math.min(newInterval[0], intervals[index][0]);
            newInterval[1] = Math.max(newInterval[1], intervals[index][1]);
            index++;
        }
        merged.add(newInterval);
        
        // 添加剩余的区间
        while (index < n) {
            merged.add(intervals[index++]);
        }
        
        return merged.toArray(new int[merged.size()][]);
    }
}

复杂度分析

时间复杂度：O(n)，其中 n 为区间的数量。遍历一次区间列表。
空间复杂度：O(n)，额外使用了一个列表存储合并后的区间。

测试和验证

编写测试用例对算法进行验证，确保其正确性和健壮性。

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        InsertInterval insertInterval = new InsertInterval();

        int[][] intervals1 = {{1, 3}, {6, 9}};
        int[] newInterval1 = {2, 5};
        System.out.println(Arrays.deepToString(insertInterval.insert(intervals1, newInterval1))); // [[1,5],[6,9]]

        int[][] intervals2 = {{1, 2}, {3, 5}, {6, 7}, {8, 10}, {12, 16}};
        int[] newInterval2 = {4, 8};
        System.out.println(Arrays.deepToString(insertInterval.insert(intervals2, newInterval2))); // [[1,2],[3,10],[12,16]]
    }
}