网站建设季度考核评价工作总结,旅游网站建设目的,wordpress 增加icon,知名的家居行业网站开发题目链接
题目简介
给定一个区间的集合#xff0c;找到需要移除区间的最小数量#xff0c;使剩余区间互不重叠。
注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”#xff0c;但没有相互重叠。
示例 1:
输入: [ [1,2], [2,3], [3,4…题目链接
题目简介
给定一个区间的集合找到需要移除区间的最小数量使剩余区间互不重叠。
注意: 可以认为区间的终点总是大于它的起点。 区间 [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解释: 你不需要移除任何区间因为它们已经是无重叠的了。
解法贪心
相信刚开始看到这道题目都冥冥之中感觉要排序和我前几天做的很类似都是需要提前固定好一个变量
我来按照右边界排序从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了。
此时问题就是要求非交叉区间的最大个数。 区间123456都按照右边界排好序。
当确定区间 1 和 区间2 重叠后如何确定是否与 区间3 也重贴呢
就是取 区间1 和 区间2 右边界的最小值因为这个最小值之前的部分一定是 区间1 和区间2 的重合部分如果这个最小值也触达到区间3那么说明 区间 123都是重合的。
接下来就是找大于区间1结束位置的区间是从区间4开始。那有同学问了为什么不从区间5开始别忘了已经是按照右边界排序的了。
区间4结束之后再找到区间6所以一共记录非交叉区间的个数是三个。
总共区间个数为6减去非交叉区间的个数3。移除区间的最小数量就是3。 代码实现 class Solution {public int eraseOverlapIntervals(int[][] intervals) {Arrays.sort(intervals, (a,b)- {return Integer.compare(a[0],b[0]);});int count 1;for(int i 1;i intervals.length;i){if(intervals[i][0] intervals[i-1][1]){intervals[i][1] Math.min(intervals[i - 1][1], intervals[i][1]);continue;}else{count;} }return intervals.length - count;}
}
