57.插入区间

题目:57.插入区间

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

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

返回插入之后的intervals。

注意 你不需要原地修改intervals。你可以创建一个新数组然后返回它。

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

• 提示：

0 <= intervals.length <= 10^4
intervals[i].length == 2
0 <= starti <= endi <= 10^5
intervals 根据 starti 按 升序 排列
newInterval.length == 2
0 <= start <= end <= 10^5

思路

1. 初始化结果列表：

   • List<int[]> result = new LinkedList<>(); 用于存储最终的区间列表。
   • int i = 0; 初始化索引 i 为 0。

2. 将所有在 newInterval 之前的区间添加到结果中：

   • 使用 while 循环，将所有结束值小于 newInterval 起始值的区间添加到结果中。

3. 合并可能重叠的区间：

   • 使用 while 循环，将所有起始值小于等于 newInterval 结束值的区间进行合并。更新 newInterval 的起始和结束值，以包含所有重叠的区间。
   • newInterval[0] = Math.min(newInterval[0], intervals[i][0]); 确保起始值为较小值。
   • newInterval[1] = Math.max(newInterval[1], intervals[i][1]); 确保结束值为较大值。

4. 将合并后的 newInterval 添加到结果中：

   • 将 newInterval 添加到结果列表中。

5. 将所有在 newInterval 之后的区间添加到结果中：

   • 使用 while 循环，将剩余的区间添加到结果列表中。

6. 将结果转换为二维数组：

   • return result.toArray(new int[result.size()][]); 将 List<int[]> 转换为二维数组返回。

• 时间复杂度:O(n)
• 空间复杂度:O(n)

代码

public int[][] insert(int[][] intervals, int[] newInterval) {
    LinkedList<int[]> result = new LinkedList<>();
    int i = 0;
    // 将所有在 newInterval 之前的区间添加到结果中
    while (i < intervals.length && intervals[i][1] < newInterval[0]) {
        result.add(intervals[i]);
        i++;
    }
    // 合并可能重叠的区间
    while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
        newInterval[0] = Math.min(intervals[i][0], newInterval[0]);
        newInterval[1] = Math.max(intervals[i][1], newInterval[1]);
        i++;
    }
    result.add(newInterval);
    // 将所有在 newInterval 之后的区间添加到结果中
    while (i < intervals.length) {
        result.add(intervals[i]);
        i++;
    }
    // 将结果转换为二维数组
    return result.toArray(new int[result.size()][]);
}