leetcode435-无重叠区间

原题

给定一个区间的集合,找到需要移除区间的最小数量,使剩余区间互不重叠。

注意:

  1. 可以认为区间的终点总是大于它的起点。
  2. 区间 [1,2] 和 [2,3] 的边界相互“接触”,但没有相互重叠。

示例1:

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

示例2:

输入: [ [1,2], [1,2], [1,2] ] 输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

示例3:

输入: [ [1,2], [2,3] ] 输出: 0
解释: 你不需要移除任何区间,因为它们已经是无重叠的了。

解法

思想

首先将所有区间按开始位置排序,相邻两个区间,如果有重叠的部分包含两种情况:

  1. 一个区间完全包含另一个区间,此时只保留较小那个区间。
  2. 一个区间的末尾位于另一个区间范围内,此时只保留前面那个区间。(两个区间完全重合或末尾重合也按这种情况处理)

这两种处理方式都是在局部范围内为后面保留更多的空间。

代码

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (array1,array2)->{
            return array1[0]-array2[0];
        });
        int lastIndex = 0;
        int deleteCount = 0;
        for(int i = 0;i<intervals.length-1;i++){
            if(intervals[lastIndex][1]>intervals[i+1][1]){
                deleteCount++;
                lastIndex = i+1;
            }else if(intervals[lastIndex][1]>intervals[i+1][0]&&intervals[lastIndex][1]<=intervals[i+1][1]){
                deleteCount++;
            }else{
                lastIndex = i+1;
            }
        }
        return deleteCount;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode435-%e6%97%a0%e9%87%8d%e5%8f%a0%e5%8c%ba%e9%97%b4/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年2月18日
下一篇 2020年2月18日

相关推荐

  • leetcode387-字符串中的第一个唯一字符

    原题 给定一个字符串,找到它的第一个不重复的字符,并返回它的索引。如果不存在,则返回 -1。 案例: s = "leetcode" 返回 0. s = "loveleetcode"…

    算法 2019年12月22日
    0130
  • leetcode22-括号生成

    原题 数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。 示例: 输入:n = 3 输出:[ "((()))", "(()())", "…

    算法 2020年4月9日
    0130
  • leetcode561-数组拆分I

    原题 给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), …, (an, bn) ,使得从1 到 n 的 min(ai, b…

    算法 2019年11月18日
    0100
  • leetcode60-第k个排列

    原题 给出集合 [1,2,3,…,n],其所有元素共有 n! 种排列。 按大小顺序列出所有排列情况,并一一标记,当 n = 3 时, 所有排列如下: "123" "132" "21…

    算法 2020年5月16日
    0110
  • leetcode64-最小路径和

    原题 给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。 说明: 每次只能向下或者向右移动一步。 示例: 输入: [ [1,3…

    算法 2020年2月24日
    0110
  • leetcode990-等式方程的可满足性

    原题 给定一个由表示变量之间关系的字符串方程组成的数组,每个字符串方程 equations[i] 的长度为 4,并采用两种不同的形式之一:"a==b" 或 "a!=b"。在这里,a…

    算法 2020年6月8日
    0100
  • leetcode234-回文链表

    原题 请判断一个链表是否为回文链表。 示例1: 输入: 1->2 输出: false 示例2: 输入: 1->2->2->1 输出: true 进阶: 你能否用 O(n) 时间复杂…

    2019年12月16日
    0120
  • leetcode341-扁平化嵌套列表迭代器

    原题 给定一个嵌套的整型列表。设计一个迭代器,使其能够遍历这个整型列表中的所有整数。 列表中的项或者为一个整数,或者是另一个列表。 示例1: 输入: [[1,1],2,[1,1]]…

    算法 2020年1月27日
    050
  • leetcode242-有效的字母异位词

    原题 https://leetcode.cn/problems/valid-anagram/description/ 解法 (针对进阶场景,若字符串中存在unicode字符) fu…

    算法 2024年3月26日
    080
  • leetcode611-有效三角形的个数

    原题 给定一个包含非负整数的数组,你的任务是统计其中可以组成三角形三条边的三元组个数。 示例1: 输入: [2,2,3,4] 输出: 3 解释: 有效的组合是: 2,3,4 (使用…

    2020年2月8日
    070

发表回复

登录后才能评论