LEETCODE-插入区间

题目描述

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

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

提示：

• 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

解题思路

• 暴力遍历法，除特殊情况以外，判断数组intervals 中的元素与newInterval 中的元素的区间大小，并按照区间划分、合并；
• 特判1：刚好在intervals 中某个元素的中间，直接覆盖后原样输出即可；
• 特判2：当前元素区间小于newInterval 中的元素区间，直接保存并退出当前循环；
• 特判3：newInterval元素区间最小，直接放到开头并原样copy输出即可；
• 特判4：对于newInterval=[0,0]的区间需要特殊处理，也是直接放到开头，再复制原有元素到新数组，返回即可。

解题编码

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        if (intervals.length == 0) {
            return new int[][]{newInterval};
        }

        if (newInterval.length == 0) {
            return intervals;
        }


        if (newInterval[0] == 0 && newInterval[1] == 0) {
            int[][] ints = new int[intervals.length + 1][];
            ints[0] = newInterval;
            System.arraycopy(intervals, 0, ints, 1, intervals.length + 1 - 1);
            return ints;
        }

        ArrayList<int[]> resultTemp = new ArrayList<>();
        boolean incloud = false;
        boolean exMark = false;
        Integer exMin = null;
        Integer exMax = null;
        Integer tempMax = Integer.MIN_VALUE;
        for (int[] currInterval : intervals) {
            // 上边界判断
            if (exMark && exMax == null) {
                // 小边界连在一起
                if (currInterval[0] == newInterval[1]) {
                    exMax = currInterval[1];
                    resultTemp.add(new int[]{exMin, exMax});
                    continue;
                }
                // 小于小边界
                if (currInterval[0] > newInterval[1]) {
                    exMax = Math.max(newInterval[1], tempMax);
                    resultTemp.add(new int[]{exMin, exMax});
                    resultTemp.add(new int[]{currInterval[0], currInterval[1]});
                    continue;
                }
                // 大边界链接
                if (currInterval[1] >= newInterval[1]) {
                    exMax = currInterval[1];
                    resultTemp.add(new int[]{exMin, exMax});
                    continue;
                }
            }

            // 替换完毕后 剩余原样输出
            if (incloud || (exMark  && exMax != null)) {
                resultTemp.add(new int[]{currInterval[0], currInterval[1]});
                continue;
            }

            // 特判1 大于区间直接跳出
            if (currInterval[1] < newInterval[0] && !exMark) {
                resultTemp.add(currInterval);
                continue;
            }

            // 特判2 包含在区间内
            if (currInterval[0] <= newInterval[0] && currInterval[1] >= newInterval[1] && !exMark) {
                resultTemp.add(currInterval);
                incloud = true;
                continue;
            }

            // 特判3 小于指定区间
            if (currInterval[0] > newInterval[1] && !exMark) {
                resultTemp.add(newInterval);
                resultTemp.add(currInterval);
                incloud = true;
                continue;
            }

            if (currInterval[0] == newInterval[1]) {
                resultTemp.add(new int[]{newInterval[0], currInterval[1]});
                incloud = true;
                continue;
            }


            // 开始交换下边界
            if (exMin == null) {
                exMin = Math.min(currInterval[0], newInterval[0]);
                tempMax = currInterval[1];
                exMark = true;
            }
        }

        if (exMark && exMax == null) {
            exMax = Math.max(newInterval[1], tempMax);
            resultTemp.add(new int[]{exMin, exMax});
        }

        if (!exMark && exMax == null && exMin == null && !incloud) {
            resultTemp.add(newInterval);
        }

        int[][] resultIntervals = new int[resultTemp.size()][];
        for (int i = 0; i < resultTemp.size(); i++) {
            resultIntervals[i] = resultTemp.get(i);
        }
        return resultIntervals;
    }
}

执行结果