Leetcode 57 | 插入区间

题目

Leetcode地址：57. 插入区间

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

**You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. 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 starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.**

示例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] 重叠。

---

解题思路

方法	时间复杂度	空间复杂度
模拟法	O(n)	O(n)

这道题使用模拟法。初看感觉很复杂，需要判断每个区间是否与newInterval重叠（有四种情况：左边界重叠、右边界重叠，包含和被包含），然后再分别对他们做合并。

仔细一想，其实我们只需要判断与newInterval不重叠的区域，剩下的就是与newInterval重叠的区域。那如何判断区间与newInterval不重叠呢？

image.png

看这张图就非常清晰了。

• 左边与newInterval不重叠的区间：右边界 < newInterval左边界
• 右边与newInterval不重叠的区间：左边界 > newInterval右边界

所以整体流程如下：

• 先处理左边与newInterval不重叠的区间：直接加入res。
• 再处理和newInterval重叠的区间，整体组成一个大的新区间，加入res。
  • 新区间左边界：min(newInterval左边界，区间左边界）
  • 新区间右边界：max(newInterval右边界，区间右边界）
• 最后处理右边与newInterval不重叠的区间：直接加入res。

Java代码

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> res = new ArrayList<>();
        int i = 0;
        // 遍历左边与newInterval不重叠的区间
        while(i < intervals.length && intervals[i][1] < newInterval[0]){
            res.add(intervals[i]);
            i++;
        }
        // 遍历中间与newInterval有重叠的部分
        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++;
        }
        res.add(newInterval);
        // 遍历右边与newInterval不重叠的区间
        while(i < intervals.length){
            res.add(intervals[i]);
            i++;
        }
        // 输出需要的答案格式
        int[][] result = new int[res.size()][2];
        for(i = 0; i < res.size(); i++){
            result[i] = res.get(i);
        }
        return result;
    }
}

总结

有些题，看起来特别复杂，其实可以通过一些思路的转换来简化问题。

比如这道题，判断两个区间是否重合，条件多，判断复杂；但是判断两个区间不重合，非常简单。所以可以通过一定的转化，把复杂的问题简单化。