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

链接

题目：

方法一：贪心

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

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

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

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

比如你面前放着 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 ！：

基本代码：
每一轮两个变量： 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

注意： 使用 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的个数即要删除的
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

注意： 这里用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; // 
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26