57.插入区间

题目

给出一个无重叠的 ，按照区间起始端点排序的区间列表。

在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

 

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

方法

本题和第56题类似。但注意本题所给的区间已经按起始端点升序排序。因此我们仍然遍历区间，按如下步骤构建结果集：

• 先将完全在新区间左边的区间（右边界都小于新区间左边界的区间）加入结果集
• 当遇到一个区间，这个区间的右边界大于等于新区间的左边界，并且这个区间的左边界小于等于新区间的右边界时，则说明需要将其合并，我们将合并后的区间作为新的要插入的区间，继续进入循环。
• 当需要合并的区间都合并完全后，将要插入的区间插入
• 最后将完全在新区间右边的区间（左边界都大于新区间右边界的区间）加入结果集

代码

public int[][] insert(int[][] intervals, int[] newInterval) {
    if(intervals == null || intervals.length == 0)
        return new int[][]{newInterval};
    int[][] res = new int[intervals.length + 1][2];
    int res_index = 0;
    int num_index = 0;
    while(num_index < intervals.length && intervals[num_index][1] < newInterval[0])
        res[res_index++] = intervals[num_index++];
    while(num_index < intervals.length && intervals[num_index][1] >= newInterval[0] && intervals[num_index][0] <= newInterval[1]){
        newInterval[0] = Math.min(intervals[num_index][0], newInterval[0]);
        newInterval[1] = Math.max(intervals[num_index][1], newInterval[1]);
        num_index++;
    }
    res[res_index++] = newInterval;
    while(num_index < intervals.length && intervals[num_index][0] > newInterval[1])
        res[res_index++] = intervals[num_index++];
    return Arrays.copyOf(res, res_index);
}