Leetcode 435. 无重叠区间——Java解题思路解析

本题是使用了贪心算法，结合Arrays.sort的重载方法

一、题目描述

题目描述 给定多个区间，计算让这些区间互不重叠所需要移除区间的最少个数。起止相连不算重叠。 输入输出样例 输入是一个数组，数组由多个长度固定为 2 的数组组成，表示区间的开始和结尾。输出一个整数，表示需要移除的区间数量。

Input: [[1,2], [2,4], [1,3]]
Output: 1

在这个样例中，我们可以移除区间 [1,3]，使得剩余的区间 [[1,2], [2,4]] 互不重叠。

二、思路

1. 贪心算法

贪心算法简单，解题分为两步：先对二维数组按照右区间进行排序；再比较当前区间右区间与下一个区间的左区间是否重合，即得出区间不重复的最大数组。 首先对二维数组按照右区间进行排序：

Arrays.sort(intervals, new Comparator<int[]>() {
          
   
            public int compare(int[] intervals1, int[] intervals2){
          
   
                    return intervals1[1] - intervals2[1];
            }
        });

这里是Arrays.sort重载的方法，详情可以查看以下链接： Arrays.sort()详解：https://www.cnblogs.com/SupremeBoy/p/12717532.html

接着按当前区间右区间与下一个区间的左区间进行比较，没有交集即证明当前右区间小于下一个区间左区间。代码如下：

int right = intervals[0][1];
        int num = 1;
        for(int i = 1; i < intervals.length; i++){
          
   
            if(intervals[i][0] >= right){
          
   
               right = intervals[i][1];
                num++;
            }
        }

完整代码：

class Solution {
          
   
    public int eraseOverlapIntervals(int[][] intervals) {
          
   
        if(intervals.length ==0 && intervals == null) return 0;
        Arrays.sort(intervals, new Comparator<int[]>() {
          
   
            public int compare(int[] intervals1, int[] intervals2){
          
   
                    return intervals1[1] - intervals2[1];
            }
        });

        int right = intervals[0][1];
        int num = 1;
        for(int i = 1; i < intervals.length; i++){
          
   
            if(intervals[i][0] >= right){
          
   
               right = intervals[i][1];
                num++;
            }
        }
        return intervals.length - num;
    }
}

运行结果：

2. 动态规划

动态规划时间复杂度较高，个人理解也不是很透彻，感兴趣的小伙伴可以查看以下链接：

Java代码：

总结

解题方法多种多样，能解出题的就是好方法，个人认为这里使用贪心的话更好处理。