Java实现 LeetCode 435 无重叠区间
2023-09-14 08:58:05 时间
435. 无重叠区间
给定一个区间的集合,找到需要移除区间的最小数量,使剩余区间互不重叠。
注意:
可以认为区间的终点总是大于它的起点。
区间 [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) {
if (intervals.length == 0) {
return 0;
}
Arrays.sort(intervals, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0];
}
});
int res = 0;
int prev = 0;
for (int i = 1; i < intervals.length; i++) {
if (intervals[prev][1] > intervals[i][0]) {
if (intervals[prev][1] > intervals[i][1]) {
prev = i;
}
res++;
} else {
prev = i;
}
}
return res;
}
}
相关文章
- Java内存模型FAQ(三)JSR133是什么?
- Java实现 LeetCode 830 较大分组的位置(暴力模拟)
- Java实现 LeetCode 814 二叉树剪枝 (遍历树)
- Java实现 LeetCode 805 数组的均值分割 (DFS+分析题)
- Java实现 LeetCode 795 区间子数组个数 (暴力分析)
- Java实现 LeetCode 783 二叉搜索树节点最小距离(遍历)
- Java实现 LeetCode 777 在LR字符串中交换相邻字符(分析题)
- Java实现 LeetCode 757 设置交集大小至少为2(排序+滑动窗口)
- Java实现 LeetCode 756 金字塔转换矩阵(DFS)
- Java实现 LeetCode 693 交替位二进制数(位运算)
- Java实现 LeetCode 690 员工的重要性(简易递归)
- Java实现 LeetCode 609 在系统中查找重复文件(阅读理解+暴力大法)
- Java实现 LeetCode 600 不含连续1的非负整数(有些题为了避免使用位运算可以换成动态规划)...
- Java实现 LeetCode 575 分糖果(看看是你的长度小还是我的种类少)
- Java实现 LeetCode 503 下一个更大元素 II
- Java实现 LeetCode 414 第三大的数
- Java实现 LeetCode 341 扁平化嵌套列表迭代器
- Java实现 LeetCode 338 比特位计数
- Java实现 LeetCode 334 递增的三元子序列
- Java实现 LeetCode 233 数字 1 的个数
- Java实现 LeetCode 225 用队列实现栈
- Java实现 LeetCode 217 存在重复元素
- Java实现 LeetCode 179 最大数
- Java实现 LeetCode 173 二叉搜索树迭代器
- Java实现 LeetCode 165 比较版本号
- Java实现 LeetCode 85 最大矩形
- Java实现 LeetCode 80 删除排序数组中的重复项 II(二)
- 【LeetCode-面试算法经典-Java实现】【066-Plus One(加一)】