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)