0057. Insert Intervals (H)

佚名 4年前 (2020-07-05) 算法 680人围观抢沙发百度已收录

Insert Interval (H)

题目

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

Example 1:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

题意

给定一个左端点递增且互不重叠的区间数组，向其中插入一个新的区间，如有重叠则需要合并，返回处理后的区间数组。

思路

先将所有右端点在新区间左端点之前的区间(即一定不会相加)插入到结果中，再将所有可以与新区间合并的区间进行合并，并加入到结果中，最后将剩余一部分不会合并的区间加入到结果中。

代码实现

Java

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> list = new ArrayList<>();
        int i = 0;
        while (i < intervals.length && intervals[i][1] < newInterval[0]) {
            list.add(intervals[i++]);
        }
        while (i < intervals.length && intervals[i][0] <= newInterval[1] && intervals[i][1] >= newInterval[0]) {
            newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
            newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
            i++;
        }
        list.add(newInterval);
        while (i < intervals.length) {
            list.add(intervals[i++]);
        }

        return list.toArray(new int[0][]);
    }
}