友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
435. 无重叠区间
给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠。
示例 1:
输入: intervals = [[1,2],[2,3],[3,4],[1,3]] 输出: 1 解释: 移除 [1,3] 后，剩下的区间没有重叠。
示例 2:
输入: intervals = [ [1,2], [1,2], [1,2] ] 输出: 2 解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
示例 3:
输入: intervals = [ [1,2], [2,3] ] 输出: 0 解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
提示:
-
1 <= intervals.length <= 105 -
intervals[i].length == 2 -
-5 * 104 <= starti < endi <= 5 * 104
思路分析
换个角度，改为计算最多可以选多少个互不重叠的区间，那么没选的区间就是要移除的区间。
首先思考一个问题：选择哪一个区间作为首个区间？
首个区间就是所有可以选择的区间中右端点最小的那个区间。
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-08-15 21:37:39
*/
public int eraseOverlapIntervals(int[][] intervals) {
// 这里是根据右边坐标点来排序
Arrays.sort(intervals, Comparator.comparingInt(a -> a[1]));
int count = 0;
int right = Integer.MIN_VALUE;
for (int i = 0; i < intervals.length; i++) {
if (right <= intervals[i][0]) {
count++;
right = intervals[i][1];
}
}
return intervals.length - count;
}