原题
给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
注意:
- 可以认为区间的终点总是大于它的起点。
- 区间 [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
解释： 你不需要移除任何区间，因为它们已经是无重叠的了。
解法
思想
首先将所有区间按开始位置排序，相邻两个区间，如果有重叠的部分包含两种情况：
- 一个区间完全包含另一个区间，此时只保留较小那个区间。
- 一个区间的末尾位于另一个区间范围内，此时只保留前面那个区间。（两个区间完全重合或末尾重合也按这种情况处理）
这两种处理方式都是在局部范围内为后面保留更多的空间。
代码
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/
相关推荐
-
leetcode990-等式方程的可满足性
原题 给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4，并采用两种不同的形式之一："a==b" 或 "a!=b"。在这里，a...
-
leetcode2-两数相加
原题 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。 如果，我们将这两个数相加起来，则会返回...
-
leetcode135-分发糖果
原题 老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。 你需要按照以下要求，帮助老师给这些孩子分发糖果： 每个孩子至少分配到 1 个...
-
leetcode41-缺失的第一个正数
原题 给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。 示例 1: 输入: [1,2,0] 输出: 3 示例 2: 输入: [3,4,-1,1] 输出: 2 示例 3...
-
leetcode198-打家劫舍
原题 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会...
-
leetcode350-两个数组的交集II
原题 给定两个数组，编写一个函数来计算它们的交集。 输入： nums1 = [1,2,2,1], nums2 = [2,2] 输出： [2,2] 示例2： 输入： nums1 = ...
-
leetcode128-最长连续序列
原题 给定一个未排序的整数数组，找出最长连续序列的长度。 要求算法的时间复杂度为 O(n)。 示例: 输入: [100, 4, 200, 1, 3, 2] 输出: 4 解释: 最长...
-
leetcode72-编辑距离
原题 给你两个单词 word1 和 word2 ，请你计算出将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作： 插入一个字符 删除一个字...
-
leetcode16-最接近的三数之和
原题 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存...
-
leetcode20-有效的括号
原题 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。 有效字符串需满足： 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序...
