算法面试8---贪心算法

1 简单贪心

贪心算法相对来说代码少，思路简单，但贪心问题的关键是确定一个问题能否使用贪心算法去解决。

例1: LeetCode 455。题解：把最大的饼干分给最贪心的还在，那么剩下的饼干中就是次大的分给次贪心的孩子即还是当前最大的饼干分给最贪心的孩子。在贪心算法中，常常要涉及到最大，最小这些数据因此常常需要进行排序。

class Solution {
    
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int i = 0,j = 0;
        int l1 = g.length,l2= s.length;
        while (i<l1 && j<l2) {
            if (g[i] <= s[j]) {
                i++; //孩子的需求被满足了，可以转到下一个孩子了
            }
            j++; //否则寻找更大的饼干
        }
        return i; //因为i是从0开始的所以直接返回便是满足孩子需求的数目
    }
}

与此类似题目：LeetCode 392。

2 贪心与动态规划的关系

例1：LeetCode 435。题目中是最少需要移除多少区间使得区间不重叠那么也可以理解为最多保留多少个区间使得区间不重叠。暴力思路就是找出所有的子区间然后判断是否重叠，为了判断重叠时方便可以先进行排序，对于组合问题大都可以用动态规划进行优化解决。如果从动态规划去理解，给定一个拍好序的区间，保留最多的区间使得区间不重叠，那么就很类似与最长上升子序列问题。

class Interval{
     int start;
     int end;
    Interval(){
        this.start = 0;
        this.end = 0;
    }
    Interval(int s,int e){
        this.start = s;
        this.end = e;
    }
}

class IntervalsComparator implements Comparator<Interval> {
    @Override
    public int compare(Interval o1, Interval o2) {
        if (o1.start != o2.start) {
            // -1：不交换位置，1：交换位置，从小到大排序
            return o1.start < o2.start ? -1 : 1;
        }
        return o1.end < o2.end ? -1 : 1;
    }
}

public class Solution {

    public int eraseOverlapIntervals(Interval[] intervals) {
        if (intervals == null || intervals.length == 0){
            return 0;
        }
        Arrays.sort(intervals, new IntervalsComparator());
        // memo[i] 表示使用intervals[0...i]的区间能构成的最长不重叠区间序列
        int[] memo = new int[intervals.length];
        // 设定初始值
        Arrays.fill(memo, 1);
        for (int i = 1; i < intervals.length; i++){
            // 求memo[i] 动态转移方程
            for (int j = 0; j < i; j++){
                if (intervals[i].start >= intervals[j].end){
                    memo[i] = Math.max(memo[i], 1 + memo[j]);
                }
            }
        }
        // 在所有的memo中取最大值
        int res = 0;
        for (int i = 0; i < intervals.length; i++){
            res = Math.max(res, memo[i]);
        }
        // 返回需要删除的区间数
        return intervals.length - res;
    }
}

可以注意到：每次选择中，每个区间的结尾很重要，结尾越小，留给后面越大的空间，后面越有可能容纳更多区间。那么贪心算法便可以采用如下思路：按照区间的结尾排序，每次选择结尾最早的，且和前一个区间不重叠的区间。

public class Solution {

    public int eraseOverlapIntervals(Interval[] intervals) {
        if (intervals == null || intervals.length == 0){
            return 0;
        }
        Arrays.sort(intervals, new IntervalsComparator());
        int res = 1;
        int pre = 0;
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i].start >= intervals[pre].end) {
                // 决定选择当前i
                res++;
                // 存储当i
                pre = i;
            }
        }
        return intervals.length - res;
    }
}

3 贪心选择性

2中使用了动态规划解决，也可以采用贪心解决，但不意味着动态规划可以解决的贪心一定能解决。上面例子中之所以能解决是因为满足了一个性质：贪心选择性：在求解最优化问题中，使用了贪心的方式选择了一组数据后，不会影响子问题的求解。因为这个性质一般正面很难去证明，所以在问题求解中一般是举出反例。如在0-1背包问题中，就举出了一个贪心算法的反例，还有如LeetCode 279中可以举出反例如下：按照贪心的思路肯定是先选择距离给定数字最接近的完全平方数那么12=9+1+1+1但是12=4+4+4才是最优的。

但有时可能是无法举出反例的，那么应该如何证明贪心算法的正确性？在算法中的证明一般常用的是两种方式：数学归纳法和反证法。在这里把问题整理下：

证明如下：

在这里给出贪心算法证明的一般思路：