57. Insert Interval 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int[][] res = new int[intervals.length + 1][];
        int resIndex = 0, i = 0;

        while (i < intervals.length && intervals[i][1] < newInterval[0]) {
            // 区间不相交，直接添加原区间至 res
            res[resIndex++] = intervals[i++];
        }
        while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
            // 关键之处：当原区间左边界小于等于新区间右边界，说明区间相交，此时合并原区间至新区间
            newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
            newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
            i++;
        }
        res[resIndex++] = newInterval;

        while (i < intervals.length) {
            // 添加剩余不相交区间
            res[resIndex++] = intervals[i++];
        }

        return Arrays.copyOf(res, resIndex);
    }
}

References

57. Insert Interval