题目

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

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

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

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

解法1

解法1的思路很简单,因为区间无重叠且按照起始点排序,那么我们可以借助56题的方法,先将newInterval插入到合适的位置,然后用56题方法合并区间。合适的位置指的是intervals[i].start <= newInterval.start但intervals[i+1].start > newInterval.start。

题目函数签名为“public int[][] insert(int[][] intervals, int[] newInterval) ”,因为插入新的区间会改变区间个数,使用int[][]不方便实现insert操作,所以我们使用容器List<int[]>来存放区间。题目要求结果存放在int[][]型数组中,我们在输出时还需要将List转换成Array。题目全部代码如下,时间复杂度O(n),空间复杂度O(n)。

import java.util.ArrayList;
import java.util.List;

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

        while (i < intervals.length) {
            int[] interval = intervals[i];

            if (newInterval != null && newInterval[0] < interval[0]) {
                inserted.add(newInterval);
                newInterval = null;
            } else {
                inserted.add(interval);
                i++;
            }
        }

        // 插入的区间比所有区间的start都大,则插入到末尾
        if (newInterval != null)
            inserted.add(newInterval);

        List<int[]> merged = new ArrayList<>();

        merged.add(inserted.get(0));

        for (i = 1; i < inserted.size(); i++) {
            int[] lastInterval = merged.get(merged.size() - 1);
            int[] currInterval = inserted.get(i);

            if (currInterval[0] <= lastInterval[1])
                lastInterval[1] = Math.max(lastInterval[1], currInterval[1]);
            else
                merged.add(currInterval);
        }

        return merged.toArray(new int[merged.size()][]);
    }
}

解法2

解法2将intervals拆分成3部分,左半部分与newInterval没有交集,右半部分与newInterval没有交集,中间部分是与newInterval有交集的区间。假设前i个intervals中的区间与newInterval没有交集,第i+1个interval与newInterval有交集,我们将这两个区间合并形成[start, end],然后i++寻找下一个区间,直到找到与newInterval不相交的区间为止。此时,我们将合并后的区间[start, end]追加到结果集,然后将intervals中剩余的区间追加到结果集。

我们分析下interval[i]与newInterval不相交,但interval[i+1]与newInterval相交有哪些情况

图1 区间相交情况

图1列出了区间相交的集中情况。从图中可以看出,当intervals[i+1]与newInterval合并的时候,我们需要取两者左边界的最小值,右边界的最大值。

图2 区间不相交的情况

在合并的过程中,我们需要判断什么时候终止。如图2所示,终止条件是当newInterval的后沿小于第i+1个区间的前沿,即newInterval.end < intervals[i+1].start。那我们用不用判断newInterval的前沿与第i个区间后沿的关系呢?是不用的!因为前面我们提到,首先寻找与newInterval不相交的区间,加入到结果集,在这个过程中,我们的判断条件就是intervals[i].end < newIntervals.start。当发生合并的时候一定有intervals[i].end >= newIntervals.start,此时我们不断的合并,直到newInterval.end < intervals[i+1].start。剩下的intervals[i+1 … end],一定不会与任何的区间相交,将它们追加到结果集即可。

全部代码如下,时间复杂度O(n),空间复杂度O(n)。解法2比解法1少了一次拷贝,所以会比解法1略快。解法1的运行时间为2ms,而解法1只用了1ms。

import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> res = new ArrayList<>();
        int i = 0;
        while (i < intervals.length && intervals[i][1] < newInterval[0]) {
            res.add(intervals[i++]);
        }

        int start = newInterval[0];
        int end = newInterval[1];
        while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
            start = Math.min(start, intervals[i][0]);
            end = Math.max(end, intervals[i][1]);
            i++;
        }
        res.add(new int[]{start, end});
        while (i < intervals.length) {
            res.add(intervals[i++]);
        }

        return res.toArray(new int[res.size()][]);
    }
}

参考:https://zxi.mytechroad.com/blog/geometry/leetcode-57-insert-interval/

pwrliang Algorithms, Array, Interval ,

Leave a Reply

Your email address will not be published. Required fields are marked *