【LeetCode】24. 57_Insert Interval · 插入区间

题目描述

英文版描述

You are given an array of non-overlapping intervals intervals where intervals[i] = [start(i), end(i)] represent the start and the end of the i(th) interval and intervals is sorted in ascending order by start(i). You are also given an interval newInterval = [start, end] that represents the start and end of another interval. Insert newInterval into intervals such that intervals is still sorted in ascending order by start(i) and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary). Return intervals after the insertion.

英文版地址

https://leetcode.com/problems/insert-interval/

中文版描述

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

示例 1：

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

输出：[[1,5],[6,9]]

示例 2：

输入：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：

输入：intervals = [], newInterval = [5,7]

输出：[[5,7]]

示例 4：

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

输出：[[1,5]]

示例 5：

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

输出：[[1,7]]

提示：

• 0 <= intervals.length <= 10^4

• intervals[i].length == 2

• 0 <= intervals[i][0] <= intervals[i][1] <= 10^5

• intervals 根据 intervals[i][0] 按 升序 排列

• newInterval.length == 2

• 0 <= newInterval[0] <= newInterval[1] <= 10^5

中文版地址

https://leetcode.cn/problems/insert-interval/

解题思路

遍历原有区间，每次分别将原区间起始值（startOld）与新区间的起始值（startNew）以及结束值（endNew）比较：

• startOld < startNew，进一步比较endOld和endNew: endOld取2者较大值

• startOld > startNew，进一步比较startOld和endNew

• startOld>endNew 直接添加区间

• startOld<endNew endOld取较大值

• 这种情况有一个问题，就是如果新区建跨了两个区间以上，就会出现区间重合的情况，所以我们需要一个变量记录前一个区间的结束值，如果后一个区间的开始值小于前一个区间的结束值则直接合并两区间（这个步骤可以在第一次遍历时进行，也可以在第一次遍历结束后单独再次进行一次比较）

解题方法

俺这版

​

class Solution {
    public static int[][] insert(int[][] intervals, int[] newInterval) {
         List<int[]> list = new ArrayList<>();
        List<Integer> listInt = new ArrayList<>();
        List<Integer> listInt2 = new ArrayList<>();
        int startNew = newInterval[0];
        int endNew = newInterval[newInterval.length - 1];
        listInt.add(startNew);
        listInt.add(endNew);
        for (int i = 0; i < intervals.length; i++) {
            int startOld = intervals[i][0];
            int endOld = intervals[i][newInterval.length - 1];
            if (startOld == startNew || startOld == endNew) {
                if (endOld == startNew || endOld == endNew) {

                } else {
                    listInt.add(endOld);
                }
            } else if (endOld == startNew || endOld == endNew) {
                if (startOld == startNew || startOld == endNew) {

                } else {
                    listInt.add(startOld);
                }
            } else {
                listInt.add(startOld);
                listInt.add(endOld);
            }

        }
        
        // 排序
        Collections.sort(listInt);

        int flag = 0;
        for (int k = 0; k < listInt.size(); k++) {
            if (listInt.get(k) == startNew) {
                if (listInt2.size() % 2 == 0) {
                    listInt2.add(listInt.get(k));
                }
                flag = k + 1;
                break;
            }
            listInt2.add(listInt.get(k));
        }

        for (int j = flag; j < listInt.size(); j++) {
            if (listInt.get(j) == endNew) {
                int step = listInt.size() - j - 1;
                if (step % 2 != 0) {
                    flag = j + 1;
                } else {
                    flag = j;
                }
                break;
            }
        }

        for (int g = flag; g < listInt.size(); g++) {
            listInt2.add(listInt.get(g));
        }

        for (int f = 0; f < listInt2.size() - 1; f++) {
            int[] temp = new int[]{listInt2.get(f), listInt2.get(f + 1)};
            list.add(temp);
            f++;
        }

        int[][] result = new int[list.size()][2];
        for (int e = 0; e < list.size(); e++) {
            result[e] = list.get(e);
        }

        return result;
    }
}

复杂度分析

• 时间复杂度：O(n)，n是数组intervals 的长度，即给定的区间个数

• 空间复杂度：O(n)，创建的List的大小n（数组intervals 的长度）一致

官方版

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;
    }
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组intervals 的长度，即给定的区间个数。

• 空间复杂度：O(1)，除了存储返回答案的空间以外，我们只需要额外的常数空间即可。

总结

这是我在正式刷题以来做的第一道中等难度的题，解题思路中的方法其实跟官方提供的更像，也是我看到这道题后的第一反应，但是写代码的时候，忽然有了把所有节点放在一起排序的想法，然后不知不觉画风就变了，于是有了现在的解法，其实在时间空间复杂度上都不如官方提供的，但也是另一种方法，算是给大家提点不一样的思路吧，有更好的方法欢迎讨论交流(*≧ω≦)