LeetCode第57题插入区间

简介: LeetCode第57题"插入区间"的解题方法,利用原区间集有序的特性,通过三步插入操作,有效实现了新区间的插入和重叠区间的合并。

继续打卡算法题,今天学习的是LeetCode第57题插入区间,这道题目是道中等题。算法题的一些解题思路和技巧真的非常巧妙,每天看一看算法题和解题思路,我相信对我们的编码思维和编码能力有一些提升。

image.png

分析一波题目

上一题56题合并区间 已经学习了怎么判断重叠区间,怎么合并区间,本题就不难了。最简单的做法,我们可以把要插入的区间和原区间集合先添加到一个新的区间集合,然后排序,最后做一次合并,后面的流程和56题一样。

        int[][] newIntervals = new int[intervals.length+1][1];
        System.arraycopy(intervals, 0, newIntervals, 0, intervals.length);
        newIntervals[newIntervals.length-1] = newInterval;
        Arrays.sort(newIntervals, (o1, o2) -> Integer.compare(o1[0], o2[0]));

通过上面的代码组成了新的区间集合,只要对newIntervals中重叠的区间进行合并,这个做法虽好理解,但是性能就降低了,因为题目已经说明原区间已经按左边界排序了,因此本题可以有更优的做法。

由于原区间集已经有序了,我们可以按如下步骤来执行插入操作。

1、将与要插入的区间无重叠的,加入到新的区间集

2、将与要插入的区间有重叠的,执行合并

3、将与要插入的区间无重叠的,加入到新的区间集

image.png

本题解题技巧

1、将原区间集分段,分为与新区间左边界偏离的一段,与新区间有重叠的,与新区间右边界偏离的一段

编码解决

重组区间集合,再排序解法

class Solution {
   
   
    public int[][] insert(int[][] intervals, int[] newInterval) {
   
   

        //存储结果
        LinkedList<int[]> result = new LinkedList<>();
        //按左边界排序
        int[][] newIntervals = new int[intervals.length+1][1];
        //重组新区间集
        System.arraycopy(intervals, 0, newIntervals, 0, intervals.length);
        newIntervals[newIntervals.length-1] = newInterval;
        Arrays.sort(newIntervals, (o1, o2) -> Integer.compare(o1[0], o2[0]));
        System.out.println(newIntervals.length);
        //第一个先加入结果
        result.add(newIntervals[0]);
        //从第二个开始判断是否重叠
        for (int i = 1; i < newIntervals.length; i++) {
   
   
            //和前面的重叠了
             System.out.println(i);
            System.out.println(newIntervals[i]);
            if (newIntervals[i][0] <= result.getLast()[1]) {
   
   
                int start = result.getLast()[0];
                int end = Math.max(newIntervals[i][1], result.getLast()[1]);
                //合并之前,最后一个需要删除
                result.removeLast();
                //合并成新区间,并加入结果
                result.add(new int[]{
   
   start, end});
            }
            else {
   
   
                //没有重叠,加入结果
                result.add(newIntervals[i]);
            }   
        }
        return result.toArray(new int[result.size()][]);
    }
}

不重组区间集且不重新排序解法

class Solution {
   
   
    public int[][] insert(int[][] intervals, int[] newInterval) {
   
   
        //存储结果
        int[][] result = new int[intervals.length + 1][2];
        int idx = 0;

        // 1、首先将新区间左边且相离的区间加入结果集
        int i = 0;
        while (i < intervals.length && intervals[i][1] < newInterval[0]) {
   
   
            result[idx++] = intervals[i++];
        }
        // 2、接着判断当前区间是否与新区间重叠,重叠的话就进行合并
        while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
   
   
            newInterval[0] = Math.min(intervals[i][0], newInterval[0]);
            newInterval[1] = Math.max(intervals[i][1], newInterval[1]);
            i++;
        }
        //合并的结果存入
        result[idx++] = newInterval;

        // 3、最后将新区间右边且相离的区间加入结果集
        while (i < intervals.length) {
   
   
            result[idx++] = intervals[i++];
        }

        return Arrays.copyOf(result, idx);
    }
}

总结

1、通过借助56题合并区间思路,可以解决本题,合并区间和判断区间重叠的方法同样适用

2、借助原区间集本身有序的特性,通过拆分3步,根据新区间和原区间集的关系,要么有交集,要么在区间集左边,执行插入操作,并且时间复杂度控制在O(n)。

相关文章
|
7月前
|
算法 测试技术 C#
【二分查找】【区间合并】LeetCode2589:完成所有任务的最少时间
【二分查找】【区间合并】LeetCode2589:完成所有任务的最少时间
|
7月前
|
算法 测试技术 C#
区间合并|LeetCode2963:统计好分割方案的数目
区间合并|LeetCode2963:统计好分割方案的数目
|
7月前
|
Go
golang力扣leetcode 56.合并区间
golang力扣leetcode 56.合并区间
78 0
|
7月前
leetcode-435:无重叠区间
leetcode-435:无重叠区间
34 0
|
2月前
|
算法
Leetcode第57题(插入区间)
LeetCode第57题“插入区间”的解题方法,包括题目描述、示例、算法思路和代码实现,旨在解决将新区间插入有序且不重叠的区间列表中,并合并重叠区间的问题。
24 0
Leetcode第57题(插入区间)
|
6月前
|
存储 算法 测试技术
力扣经典150题第四十七题:汇总区间
力扣经典150题第四十七题:汇总区间
49 1
|
6月前
|
存储 SQL 算法
高效日程管理:利用区间合并算法优化活动安排【python LeetCode57】
高效日程管理:利用区间合并算法优化活动安排【python LeetCode57】
|
6月前
|
存储 算法 搜索推荐
掌握区间合并:解决实际问题的算法策略和应用案例【python LeetCode题目56】
掌握区间合并:解决实际问题的算法策略和应用案例【python LeetCode题目56】
|
6月前
|
存储 算法 数据可视化
【模拟面试问答】深入解析力扣163题:缺失的区间(线性扫描与双指针法详解)
【模拟面试问答】深入解析力扣163题:缺失的区间(线性扫描与双指针法详解)
|
6月前
|
存储 算法 测试技术
力扣经典150题第四十九题:插入区间
力扣经典150题第四十九题:插入区间
27 0