LeetCode 435.无重叠区间题目地址:
https://leetcode-cn.com/problems/non-overlapping-intervals/
题目描述:
给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
注意:
1. 可以认为区间的终点总是大于它的起点。
2. 区间 [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
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
题目分析:
输入是一个二维数组，数组里面存放的是区间范围，我们应该采取的贪心策略应该为:选择区间结尾更小，且不相交的区间。因为选择区间结尾越小，留给其它区间的空间范围越大。我们可以先对区间的结尾大小进行排序，每次选择结尾最小，并且和前面一个选择的区间不重叠的区间。将不重叠的区间保留，把重叠的区间剔除，就可以得到不重叠的最多区间数，也就可以得到移除区间的最少个数。
题解一:
执行用时: 5 ms
内存消耗: 38.2 MB
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
// 如果数组为空，直接返回0
if (intervals.length == 0)
{
return 0;
}
// 定义变量存放区间个数
int size = intervals.length;
// 自定义排序，按照区间第二个数从小到大进行排序
Arrays.sort(intervals, Comparator.comparingInt(o -> o[1]));
// 定义变量临时存放区间右端点值，首先把第一个区间右端点值赋给此临时变量
int right = intervals[0][1];
// 定义保留的区间个数，第一个区间默认保留
int retain = 1;
// 从第二个区间开始，依次遍历所有区间
for (int i = 1; i < size; ++i)
{
// 如果当前区间左端点值大于或等于前一个区间右端点值
if (intervals[i][0] >= right)
{
// 保留区间此区间，保留区间数加一
++retain;
// 把当前区间右端点值赋予临时变量
right = intervals[i][1];
}
}
// 返回移除区间个数，即所有区间个数减去保留区间个数
return size - retain;
}
}题解二:
执行用时: 2 ms
内存消耗: 38.2 MB
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
// 自定义排序，按照区间第一个数从小到大进行排序
Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
// 定义变量临时存放区间右端点值，首先把第一个区间右端点值赋给此临时变量
int end = intervals[0][1];
// 定义变量存放移除区间的个数
int count = 0;
// 从第二个区间开始，依次遍历所有区间
for (int i = 1; i < intervals.length; i++)
{
// 如果当前区间左端点值小于前一个区间右端点值，此区间需移除
if (intervals[i][0] < end)
{
// 右端点值取临时右端点值与当前区间右端点值的最小值
end = Math.min(end, intervals[i][1]);
// 此区间移除，移除区间数加一
count++;
}
else // 如果区间刚好满足保留条件，临时右端点值更新为当前区间右端点值
end = intervals[i][1];
}
// 返回移除区间的个数
return count;
}
}题目来源:力扣(LeetCode)
欢迎关注我的公众号，和我一起学习，一起成长！