leetCode日记--57. Insert interval

碎碎念:感觉川皇要赢了啊。。出国又要卷起来了,米国大佬全部出不去了。。

题目如下:

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

Example 3:

Input: intervals = [], newInterval = [5,7]
Output: [[5,7]]

Example 4:

Input: intervals = [[1,5]], newInterval = [2,3]
Output: [[1,5]]

Example 5:

Input: intervals = [[1,5]], newInterval = [2,7]
Output: [[1,7]]

思路:

方法一:

本题与前几天写的这题(也是区间问题)有一定的相关性,就是在二维数组中的区间起始值是有序的情况下,一个一个合并相邻的区间。

代码如下:

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        if(intervals.length==0)
            return new int [][] {newInterval};
        int[][]res = new int[intervals.length+1][] ;
        int i=0,flag=0;
        for(int[] a : intervals){
            if(a[0]<newInterval[0]||flag==1)
                res[i] = a;
            else{
                res[i] = newInterval;
                res[++i] = a;
                flag=1;
            }
            i+=1;
        }
        if(flag==0)
            res[i]=newInterval;
        List<int[]> temp = new ArrayList<int[]>();
        temp.add(res[0]);
        for( i=0;i<res.length-1;i++){
            if(temp.get(temp.size()-1)[1]>=res[i+1][0])
                temp.get(temp.size()-1)[1] = Math.max(temp.get(temp.size()-1)[1],res[i+1][1]);
            else
                temp.add(res[i+1]);
        }
        return temp.toArray(new int[temp.size()][]);
    }
}

官方题解思路如下:

官方题解和我的思路差不多,主要就是少排序一次,因为题目已经说明有序,因此遍历的时候进行合并就可以。

在给定的区间集合 X 互不重叠的前提下,当我们需要插入一个新的区间 S=[left,right] 时,我们只需要:

找出所有与区间 S 重叠的区间集合X
将 X中的所有区间连带上区间 S 合并成一个大区间;
最终的答案即为不与X重叠的区间以及合并后的大区间。

补充一个数学知识:

对于两个有交集的区间:

他们的交集为[max(l1,l2),min(r1,r2)].

他们的并集为[min(l1,l2),max(r1,r2)].

然后我们依次遍历,在遍历中合并就可以了。

代码如下:

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)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注