• 想要精通算法和SQL的成长之路 - 无重叠区间


    想要精通算法和SQL的成长之路 - 无重叠区间

    前言

    想要精通算法和SQL的成长之路 - 系列导航

    一. 无重叠区间

    原题链接

    给定一个区间的集合 intervals ,其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量,使剩余区间互不重叠 。

    示例1:

    • 输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
    • 输出: 1
    • 解释: 移除 [1,3] 后,剩下的区间没有重叠。

    首先呢,既然题目给定的N个区间中,我们假设肯定有重叠的部分,那么我们怎么去判断某一部分的区间是重叠的呢?那肯定是需要比较相邻两个区间的左右边界。更重要的是,我们需要对给定的区间做一个排序。以便于比较。

    那么如何做到减少最少数量的区间以达到题目要求?

    核心思想:尽可能保证每个区间的范围越小越好。那么重叠的概率也就越小。

    那么排序的时候这就需要分两种情况来考虑。

    思路一:按照右边界来排序。那么我们应该从左往右进行遍历。那么右边界越小越好(局部最优)。右边界越小,留给下一个区间的范围可能就越大。存在交集的可能越小。那么需要删除的区间个数越少。(全局最优

    思路二:按照左边界来排序。那么我们应该从右往左进行遍历。那么左边界越大越好。左边界越大,留给上一个区间的范围可能就越大。

    以右边界排序为例,如图:
    在这里插入图片描述

    我画了6个区间:分别进行了标号。也能看出来根据右边界进行排序。

    1. 第二个区间和第三个区间都和黄色虚线位置存在交集,那么这两个区间应该被删除。
    2. 找到第一个与黄色虚线不存在交集的区间,它的右边界作为新的交际线。也就是区间4。
    3. 同理,第一个和区间4不存在交集的也就是区间6。区间5存在交集。

    那么遍历的过程中计入存在交集的个数,即是最终要删除的个数。

    以按照右边界排序为例,最终结果:

    public int eraseOverlapIntervals(int[][] intervals) {
        // 根据右边界从小到大排序
        Arrays.sort(intervals, (o1, o2) -> o1[1] - o2[1]);
        int count = 0;
        int pre = Integer.MIN_VALUE;
        // 从左往右遍历,希望右边界越小越好
        for (int i = 0; i < intervals.length; i++) {
            // 上一个右边界(没有重复的) > 当前区间的左边界, 说明当前区间出现交集
            if (pre > intervals[i][0]) {
                // 记录交集的个数,也就是要删除的区间个数
                count++;
            } else {
                // 更新右边界
                pre = intervals[i][1];
            }
        }
        return count;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
  • 相关阅读:
    激光共聚焦如何选择荧光染料
    4.2串的模式匹配(含KMP算法)
    使用JAXB将xml转成Java对象
    vue - 路由守卫
    【网络安全】文件包含漏洞--通过日志投毒getshell
    win11点击任务栏固定的应用:该文件没有与之关联的应用来执行该操作
    vulnhub BTRSys: v2.1
    域名是什么 有什么用
    【Leetcode每日一题:1106.解析布尔表达式~~~栈+模拟+计数+位运算】
    JDK11设置参数说明
  • 原文地址:https://blog.csdn.net/Zong_0915/article/details/128052275