LeetCode 435：无重叠区间（贪心）

红太狼 2024-04-07 13:20 65阅读 0赞

[链接][Link 1]

**题目**：  
![在这里插入图片描述][0d028bfa40c443c79c6ed7009fe8e271.png]

### 方法一：贪心 ###

**什么是贪心算法 ?**  
贪心算法可以认为是动态规划算法的一个特例，相比动态规划，使用贪心算法需要满足更多的条件（贪心选择性质），但是效率比动态规划要高。

比如说一个算法问题使用暴力解法需要指数级时间，如果能使用动态规划消除重叠子问题，就可以降到多项式级别的时间，如果满足贪心选择性质，那么可以进一步降低时间复杂度，达到线性级别的；

**什么是贪心选择性质？**  
简单说就是：**每一步都做出一个局部最优的选择，最终的结果就是全局最优**。

注意：这是一种特殊性质，其实只有一部分问题拥有这个性质；

比如你面前放着 100 张人民币，你只能拿十张，怎么才能拿最多的面额？显然每次选择剩下钞票中面值最大的一张，最后你的选择一定是最优的；

#### 思路： ####

1.  **先以区间 `end` 为基准从小到大排序**，然后从区间集合 intvs 中选择一个区间 x，这个 x 是在当前所有区间中**结束最早**的（**end 最小**）。
2.  **如果下一个区间的start >= 上一个区间的x\_end，才不重叠，可以放入x，count++, ！**
3.  重复步骤 1 和 2，直到 intvs 为空为止，不重叠的就是所有x；

**【排完序以后】，所有与 x 相交的区间必然会与 x 的 end 相交**；**如果一个区间不想与 x 的 end 相交，它的 start 必须要 ＞= x 的 end ！**：  
![在这里插入图片描述][43d3dde1d3a94d8c9b336c8ff11fc21d.png]

**基本代码**：  
每一轮两个变量： x\_end和下一个区间k的start ； 结尾更新 x\_end即为当前k的end；

public int intervalSchedule(int[][] intvs) {
        
        if (intvs.length == 0) return 0;
        // 按 end 升序排序
        Arrays.sort(intvs, new Comparator<int[]>() {
        
            public int compare(int[] a, int[] b) {
        
                return a[1] - b[1];
            }
        });
        // 至少有一个区间不相交
        int count = 1;
        // 排序后，第一个区间就是 x
        int x_end = intvs[0][1];
        for (int[] interval : intvs) {
        
            int start = interval[0];
            if (start >= x_end) {
        
                // 找到下一个选择的区间了
                count++;
                x_end = interval[1];
            }
        }
        return count;
    }

**注意**： 使用 for-each 循环，第一次会判断第一个区间的end和自己的start，由于不满足不重叠条件，所以count不会++；

**`即只统计不重叠的情况！最简单 ！`**  
针对此题，先算出不重叠的x个数，再用总的个数减去x个数即为要删除的！

#### Java实现： ####

class Solution {
        
        public int eraseOverlapIntervals(int[][] intervals) {
        
            // 贪心
            // 排序
            Arrays.sort(intervals,new Comparator<int[]>(){
        
                @Override
                public int compare(int[] a,int[] b){
          //比较的是intervals的元素即一维数组
                    return a[1]-b[1]; // 以end来排序
                }
            });
            //
            int n=intervals.length;
            int count=1; // 不重叠的区间 x个数
            int x_end=intervals[0][1]; // 第一个区间的end
            for(int i=1;i<n;i++){
        
                // 逐个判断
                int start=intervals[i][0]; // x_end的下一个区间的start
    
                if(start >= x_end){
         // 下一个start >=上一个的end，才不重叠，放入x
                    count++;
                    x_end=intervals[i][1];
                }
            }
            return n-count; // 总的减去不重叠的x的个数即要删除的
        }
    }

**注意**： 这里用for 循环从1开始，跳过了第一个，从0开始也可以，自己的 start一定小于end ，所以会跳过执行下一次循环，不影响结果；

或使用for-each

class Solution {
        
        public int eraseOverlapIntervals(int[][] intervals) {
        
            // 贪心
            // 排序
            Arrays.sort(intervals,new Comparator<int[]>(){
        
                @Override
                public int compare(int[] a,int[] b){
          //比较的是intervals的元素即一维数组
                    return a[1]-b[1]; // 以end来排序
                }
            });
            //
            int n=intervals.length;
            int count=1; // 不重叠的区间 x个数
            int x_end=intervals[0][1]; // 第一个区间的end
            for(int[] k:intervals){
        
                // 逐个判断
                int start=k[0]; // x_end的下一个区间的start
    
                if(start >= x_end){
         // 下一个start >=上一个的end，才不重叠，放入x
                    count++;
                    x_end=k[1];
                }
            }
            return n-count; // 
        }
    }

[Link 1]: https://leetcode.cn/problems/non-overlapping-intervals/
[0d028bfa40c443c79c6ed7009fe8e271.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/dc1855b8422143eca6182b6a080eae8a.png
[43d3dde1d3a94d8c9b336c8ff11fc21d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/3eb72ebe4b814323824dccd5fb468d04.png