057. Insert-Interval

difficulty: Hard

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.

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].

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

Method One

主要是把问题分成三部分，之前和之后的直接加上。 中间的需要处理一下。

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        if(intervals.length < 1) {
            return new int[][]{{newInterval[0], newInterval[1]}};
        }
        ArrayList<int[]> ans = new ArrayList<>();
​
        int i = 0;
        while( i < intervals.length && intervals[i][1] < newInterval[0] ) {
            ans.add(intervals[i]);
            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++;
        }
        ans.add(newInterval);
​
        while( i < intervals.length ){
            ans.add(intervals[i]);
            i++;
        }
​
        int[][] res = new int[ans.size()][2];
        for(int j = 0; j < ans.size(); j++ ){
            res[j][0] = ans.get(j)[0];
            res[j][1] = ans.get(j)[1];
        }
        return res;
    }
}
​

2022

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        ArrayDeque<int[]> ans = new ArrayDeque<>();
        int i = 0;
        while(i < intervals.length && intervals[i][1] < newInterval[0]){
            ans.add(intervals[i]);
            i++;
        }
        while(i < intervals.length && intervals[i][0] <= newInterval[1]){
            newInterval = mergeTwo(newInterval, intervals[i]);
            i++;
        }
        ans.add(newInterval);
        while(i < intervals.length){
            ans.add(intervals[i]);
            i++;
        }
        return ans.toArray(new int[ans.size()][]);
    }
    private int[] mergeTwo(int[] a, int[] b){
        return new int[]{Math.min(a[0], b[0]), Math.max(a[1], b[1])};
    }
}

2023 代码

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        ArrayList<int[]> list = new ArrayList<>();
        boolean inserted = false;
        for (int[] interval : intervals) {
            if (inserted || interval[1] < newInterval[0]) {
                list.add(interval);
            } else if (interval[0] > newInterval[1]) {
                list.add(newInterval);
                list.add(interval);
                inserted = true;
            } else {
                newInterval[0] = Math.min(newInterval[0], interval[0]);
                newInterval[1] = Math.max(newInterval[1], interval[1]);
            }
        }
        if (!inserted) {
            list.add(newInterval);
        }
        int[][] ans = new int[list.size()][2];
        for (int i = 0; i < list.size(); i++) {
            ans[i] = list.get(i);
        }
        return ans;
    }
}