给定一个区间的集合,找到需要移除区间的最小数量,使剩余区间互不重叠。
注意:
可以认为区间的终点总是大于它的起点。
区间 [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] 来使剩下的区间没有重叠。
思路:为了使删除的数量最下,达到不重叠,那么尽量去删除区间范围大的。
根据区间的后一个值进行排序。那么区间后一个值大的就会被排序到后面。
但是,他们这个数组里的数,就算进行排序后,区间也应该是尽量隔离,并且递增排序的。
for循环判断即可。当第一个值大于后一个值的第一个值,那么删除个数加1.否则,递增下一个即可。
这里贪心的是:以区间后一个值进行排序,贪后一个值过大,导致>它的后一个区间的第一个值。
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
if(intervals.length <= 0 || intervals.length == 1)
return 0;
Arrays.sort(intervals, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[1]-o2[1];
}
});
int nums = intervals[0][1];
int numbers = 0;
for(int i = 1;i < intervals.length;i++)
{
if(nums > intervals[i][0])
{
numbers++;
continue;
}
nums = intervals[i][1];
}
return numbers;
}
}