435. 无重叠区间(leetcode)
https://leetcode.cn/problems/non-overlapping-intervals/description/
贪心:思路是更新重叠的区间
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
// 区间问题,首先排序,找到发生重叠的两个区间,将右边的重叠区间移除,实际对应代码的操作是
// 将右边的区间右端点更新为(左区间和右区间)的最左端点,然后res就可以++
// 这里更新右端点是其实意味着可以选择删除这两个区间的其中一个,
// 如果右区间的右端点比左区间的右端点偏左,则删除左区间,反之其实是删除右区间
Arrays.sort(intervals,(a,b) -> Integer.compare(a[0],b[0]));
int res=0;
for(int i=1;i<intervals.length;i++)
{
// 左区间的右端点 在 在右区间的左端点的 右边 ,即发生重叠
if(intervals[i-1][1] > intervals[i][0])
{
// 发生重叠,更新右区间
intervals[i][1]=Math.min(intervals[i-1][1],intervals[i][1]);
res++;
}
}
return res;
}
}