【Easy】30. Insert Interval

Given a non-overlapping interval list which is sorted by start point.

Insert a new interval into it, make sure the list is still in order and non-overlapping (merge intervals if necessary).

Example:

Insert (2, 5) into [(1,2), (5,9)], we get [(1,9)].

Insert (3, 4) into [(1,2), (5,9)], we get [(1,2), (3,4), (5,9)].

解题思路

维护left和right两个数组，把所有end小于newInterval的start的区间放入left，把所有start大于newInterval的end的区间放入righ。 中间有交集的部分取最小的start和最大的end。

核心代码

    int start = newInterval.start, end = newInterval.end;

    for (int i = 0; i < intervals.size(); i++){
        if (intervals.get(i).end < newInterval.start) left.add(intervals.get(i));
        else if (intervals.get(i).start > newInterval.end) right.add(intervals.get(i));
        else {
            start = Math.min(start, intervals.get(i).start);
            end = Math.max(end, intervals.get(i).end);
        }
    }

    result.addAll(left);
    result.add(new Interval(start, end));
    result.addAll(right);

时间空间复杂度

O(n) + S(n)

n为数组长度