贪心

Assign Cookies 455

饼干和孩子都排序，最大的饼干总是给最贪婪的孩子，如果最大的饼干都满足不了最贪婪的孩子，那么对不起他太贪婪了。。去找次贪婪的孩子。

    public int findContentChildren(int[] g, int[] s) {
        if(g == null || s == null || g.length == 0 || s.length == 0){
            return 0;
        }
        Arrays.sort(g);
        Arrays.sort(s);
        int i = g.length - 1;
        int j = s.length - 1;
        int ans = 0;
        while(i >= 0 && j >= 0){//i>=0是还有人 j>=0是还有饼干
            if(g[i] <= s[j]){
                ans ++;
                i--;
                j--;
            }else{
                i--;
            }
        }
        
        return ans;
    }

Non-overlapping Intervals 435

把给定的区间集合通过删除区间，让它们互不重叠，求最少删除几个区间？贪心的策略是，每次选择留下哪个区间时候，这个区间的结尾很关键，结尾越小，留给剩下的区间的空间越大，这样就尽可能能够容纳更多的区间了，也就能尽可能少的删除区间。
所以我们先按区间结尾对区间进行排序，然后逐一判断，下一个区间的start是不是比前一个区间的end要大或者相等，大或者相等就能容纳，如果小就丢弃。

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
class Solution {
    public int eraseOverlapIntervals(Interval[] intervals) {
        if(intervals == null || intervals.length <= 1){
            return 0;
        }        
        Arrays.sort(intervals, new Comparator<Interval>(){
            public int compare(Interval i1, Interval i2){
                return i1.end - i2.end;
            }
        });
        int prevEnd = intervals[0].end;
        int ans = 0;
        for(int i = 1; i < intervals.length; i++){
            if(intervals[i].start < prevEnd){
                ans ++;
            }else{
                prevEnd = intervals[i].end;
            }
        }
        
        return ans;
    }
}

贪心和动态规划的区别

二者都要求原问题有最优子结构，即一个问题的最优解可以由这个问题的子问题的最优解有效构造出来。
贪心——壮士断腕，如果选择了就不后悔。
动态规划——笑到最后，暂时的领先代表不了什么。

贪心的证明举例

很多时候贪心算法。。我们都是靠直觉去做，能举出反例的话就能证明这样贪心是错误的，比如0-1背包问题，就不能使用贪心。但是有时候并不能举出反例，那么怎么去正向证明结论正确？

算法设计中，数学证明一般会采用反证法和数学归纳法，贪心选择性质可以使用反证法来证明。
以上面那个问题为例：

什么叫不影响后续的区间选择？就是选择s(i),f(i)和选择最优解s(j),f(j)的结果是一样的。为什么是一样的，第一，前端s(i)去替换s(j)，这个问题的假设前提肯定是前面的所有区间选择对目前的两种选择是一样的，由于选择都是合法的，所以s(i)和s(j)都不会和前面选择的末端重合，换来换去没有影响，而后端f(i)去替换f(j)，由于f(i)结束的早一些，后端结束更早，那么最优解后面的后续区间的选择都不会受到影响。而最优解后续的选择是固定的。那么是不是s(i),f(i)的选择也能得到最优解？也就是我们的贪心策略可以得到最优解，那么和假设就矛盾了，假设最多只能得到k-1,但却反证出来了k。那么假设不成立！

证明的思路是这样的：