题目描述
给定一个区间的集合,找到需要移除区间的最小数量,使剩余区间互不重叠。
注意:
- 可以认为区间的终点总是大于它的起点。
- 区间 [1,2] 和 [2,3] 的边界相互“接触”,但没有相互重叠。
贪心算法介绍:
贪心算法可以认为是动态规划算法的一个特例,相比动态规划,使用贪心算法需要满足更多的条件(贪心选择性质),但是效率比动态规划要高。贪心选择性质简单说就是:每一步都做出一个局部最优的选择,最终的结果就是全局最优。
解题思路:
- 首先求出最大不重复区间
max
- 从区间集合
intvs
中选择一个区间x
,这个x
是在当前所有区间中结束最早的(end
最小) - 把所有与
x
区间相交的区间从区间集合intvs
中删除 - 重复步骤 1 和 2,直到
intvs
为空为止。之前选出的那些x
就是最大不相交子集
- 从区间集合
- 总的区间数
length
减去最大不重复区间max
,length-max
即为所求
static int eraseOverlapIntervals(int[][] intervals) {
int length = intervals.length;
int max = maxIntervals(intervals);
return length - max;
}
static int maxIntervals(int[][] intervals) {
Arrays.sort(intervals, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[1] - o2[1];
}
});
int count = 1;
int x_end = intervals[0][1];
for (int[] interval : intervals) {
int start = interval[0];
if (start >= x_end) {
count++;
x_end = interval[1];
}
}
return count;
}
Q.E.D.