50.插入区间

题目

给你一个 无重叠的 ，按照区间起始端点排序的区间列表 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 <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 105
• intervals 根据 starti 按 升序 排列
• newInterval.length == 2
• 0 <= start <= end <= 105

思路

• 题目说了是无重叠的按照区间起始端点排序的，所以不用排序了。

• 用指针去扫 intervals，最多可能有三个阶段:

  • 不重叠的绿区间，在蓝区间的左边
  • 有重叠的绿区间
  • 不重叠的绿区间，在蓝区间的右边

• 逐个分析

  • 不重叠，需满足：绿区间的右端，位于蓝区间的左端的左边，如 [1,2]。

    • 则当前绿区间，推入 res 数组，指针 +1，考察下一个绿区间。

    • 循环结束时，当前绿区间的屁股，就没落在蓝区间之间，有重叠了，如 [3,5]。

      • 现在看重叠的。我们反过来想，没重叠，就要满足：绿区间的左端，落在蓝区间的屁股的后面，反之就有重叠：绿区间的左端 <= 蓝区间的右端，极端的例子就是 [8,10]。

    • 和蓝有重叠的区间，会合并成一个区间：左端取蓝绿左端的较小者，右端取蓝绿右端的较大者，不断更新给蓝区间。

    • 循环结束时，将蓝区间（它是合并后的新区间）推入 res 数组。
      • 剩下的，都在蓝区间右边，不重叠。不用额外判断，依次推入 res 数组。

class Solution {
    fun insert(intervals: Array<IntArray>, newInterval: IntArray): Array<IntArray> {
        val res = mutableListOf<IntArray>()
        val len = intervals.size
        var i = 0

        while (i < len && intervals[i][1] < newInterval[0]) {
            res.add(intervals[i])
            i++
        }

        while (i < len && intervals[i][0] <= newInterval[1]) {
            if (intervals[i][0] < newInterval[0]) {
                newInterval[0] = intervals[i][0]
            }
            if (intervals[i][1] > newInterval[1]) {
                newInterval[1] = intervals[i][1]
            }
            i++
        }
        res.add(newInterval)

        while (i < len) {
            res.add(intervals[i])
            i++
        }

        return res.toTypedArray()
    }
}

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        ArrayList<int[]> res = new ArrayList<>();
        int len = intervals.length;
        int i = 0;
        // 判断左边不重合
        while (i < len && intervals[i][1] < newInterval[0]) {
            res.add(intervals[i]);
            i++;
        }
        // 判断重合
        while (i < len && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = Math.min(intervals[i][0], newInterval[0]);
            newInterval[1] = Math.max(intervals[i][1], newInterval[1]);
            i++;
        }
        res.add(newInterval);
        // 判断右边不重合
        while (i < len && intervals[i][0] > newInterval[1]) {
            res.add(intervals[i]);
            i++;
        }
        return res.toArray(new int[0][]);
    }
}

复杂度分析:

• 时间复杂度：O(n)，其中 n 是数组 intervals 的长度，即给定的区间个数。

• 空间复杂度：O(n)。

• 下一题

• 邮箱 ：charon.chui@gmail.com
• Good Luck!