插入区间

2020-11-23

57. 插入区间

难度：中等

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

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

示例 1：

1 2	输入：intervals = [[1,3],[6,9]], newInterval = [2,5] 输出：[[1,5],[6,9]]

示例 2：

1
2
3

输入：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] 重叠。

示例 3：

1 2	输入：intervals = [], newInterval = [5,7] 输出：[[5,7]]

示例 4：

1 2	输入：intervals = [[1,5]], newInterval = [2,3] 输出：[[1,5]]

示例 5：

1 2	输入：intervals = [[1,5]], newInterval = [2,7] 输出：[[1,7]]

提示：

0 <= intervals.length <= 104
intervals[i].length == 2
0 <= intervals[i][0] <= intervals[i][1] <= 105
intervals 根据 intervals[i][0] 按升序排列
newInterval.length == 2
0 <= newInterval[0] <= newInterval[1] <= 105

模拟

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        if (intervals.length == 0 || intervals[0].length == 0) {
            return new int[][]{newInterval};
        }
        List<int[]> list = new ArrayList<>();

        boolean flag = true;
        for (int i = 0; i < intervals.length; i++) {
            // 如果存在交叉
            if ((intervals[i][0] <= newInterval[0] && intervals[i][1] >= newInterval[0]) ||
                    (intervals[i][1] >= newInterval[0] && intervals[i][0] <= newInterval[1])) {
                int min = Math.min(intervals[i][0], newInterval[0]);
                int max = Math.max(intervals[i][1], newInterval[1]);
                // 如果当前结果的最大右边界小于当前的最小值，那么移除原先结果中的区间
                if (list.size() > 0 && list.get(list.size() - 1)[1] >= min) {
                    min = list.get(list.size() - 1)[0];
                    list.remove(list.size() - 1);
                }
                // 加入更新后的区间
                list.add(new int[]{min, max});
                flag = false;
            } else {
                // 如果不存在交叉，直接插入
                list.add(intervals[i]);
            }
        }
        // 处理边界条件
        if (flag) {
            flag = false;
            for (int i = 0; i < list.size(); i++) {
                if (list.get(i)[0] > newInterval[1]) {
                    list.add(i, newInterval);
                    flag = true;
                    break;
                }
            }
            if (!flag) {
                list.add(newInterval);
            }
        }
        // 返回结果
        int[][] res = new int[list.size()][2];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }
}

优雅的写法


class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int left = newInterval[0];
        int right = newInterval[1];
        boolean placed = false;
        List<int[]> ansList = new ArrayList<int[]>();
        for (int[] interval : intervals) {
            if (interval[0] > right) {
                // 在插入区间的右侧且无交集
                if (!placed) {
                    ansList.add(new int[]{left, right});
                    placed = true;                    
                }
                ansList.add(interval);
            } else if (interval[1] < left) {
                // 在插入区间的左侧且无交集
                ansList.add(interval);
            } else {
                // 与插入区间有交集，计算它们的并集
                left = Math.min(left, interval[0]);
                right = Math.max(right, interval[1]);
            }
        }
        if (!placed) {
            ansList.add(new int[]{left, right});
        }
        int[][] ans = new int[ansList.size()][2];
        for (int i = 0; i < ansList.size(); ++i) {
            ans[i] = ansList.get(i);
        }
        return ans;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/insert-interval/solution/cha-ru-qu-jian-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

作者：LeetCode-Solution来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。