贪心：每次都选局部最优解

思想很简单的贪心

贪心算法是在每一步选择中都采取当前最好的或者最优的选择，从而导致最终的结果是最好的或者最优的。贪心算法可以解决解决一些最优化问题，如求图中的最小生成树，求哈夫曼编码。算法的思想还是比较容易理解的，难的是问题能否用贪心解决，贪心的具体策略是什么？

如，给你一箱苹果，最多只能拿三个，你会怎么选择？ 肯定每次都是拿最大的了，这样最终拿到的苹果肯定是最重的

但是有些问题，如果每次都是选择局部最优解，有可能最终结果不是最优解 如有这样一个数塔，一个人可以从一个格子移动到和它相邻的2个格子，从塔顶到塔底移动路径的最大值是多少？

如果采用贪心策略，每次都选择下一层的最大值，那么最终走过的路径是1->7->2->2，显然不是最优解（最优解是1->5->10->10）

其实这种问题我们可以用动态规划来解决，后续再聊

区间问题

给你n个课程表，以及每节课的开始时间和结束时间，问你最多能学多少门课？ 注意：当a课程的结束时间和b课程的开始相同时，a课程和b课程能同时学

示例 1:

输入: [ [1,2], [2,3], [3,4], [1,3] ]
输出: 3
解释: 最多能学3门课程，即前3门

示例 2:

输入: [ [1,2], [1,2], [1,2] ]
输出: 1
解释: 最多能学一门课程，因为时间都一样

当我们使用贪心算法时，会发现贪心的策略有如下几种

1. 每次选择选结束时间最早的课
2. 每次选开始时间最早的课

我们多测几个例子就能发现每次选择选结束时间最早的课是最优的贪心策略（一般我们不做严格的数学证明，只是多造几个测试用例，然后验证我们的想法）

每次选开始时间最早的课并不是最优的贪心策略，比如课程课程的开始时间和结束时间示意图

如果每次选择开始时间最早的课，选择的课程为1，3

如果每次选择结束时间最早的课，选择的课程为1，4，5

public int eraseOverlapIntervals(int[][] intervals) {
     // 按照每个数组的第二个元素升序排序
     Arrays.sort(intervals, (a, b) -> (a[1] - b[1]));
     int end = intervals[0][1];
     int sum = 1;
     for (int i = 1; i < intervals.length; i++) {
         if (intervals[i][0] >= end) {
             sum++;
             end = intervals[i][1];
         }
     }
     return sum;
 }

就这个区间问题，能衍生出很多问法，如LeetCode 435. 无重叠区间

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

注意:

可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。

示例 1:

输入: [ [1,2], [2,3], [3,4], [1,3] ]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。

这道题的解题思路和上面这个基本上没有区别，只是最后要求的是移除的区间。用总的区间减去符合要求的最长区间即可

public int eraseOverlapIntervals(int[][] intervals) {
    if (intervals.length == 0) {
        return 0;
    }
    // 按照每个数组的第二个元素升序排序
    Arrays.sort(intervals, (a, b) -> (a[1] - b[1]));
    int end = intervals[0][1];
    int sum = 1;
    for (int i = 1; i < intervals.length; i++) {
        if (intervals[i][0] >= end) {
            sum++;
            end = intervals[i][1];
        }
    }
    return intervals.length - sum;
}

分发饼干

题目来源：LeetCode 455.分发饼干

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i ，都有一个胃口值 gi ，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j ，都有一个尺寸 sj 。如果 sj >= gi ，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

注意：

你可以假设胃口值为正。 一个小朋友最多只能拥有一块饼干。

示例 1:

输入: [1,2,3], [1,1]
输出: 1
解释: 
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。

示例 2:

输入: [1,2], [1,2,3]
输出: 2
解释: 
你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.

现实生活中很容易遇到这种问题哈，想想你会怎么做？

我们可以让小孩按照饭量从小到大排队，同时将并饼干从小到大放好，尽量用最小的饼干满足每个小孩，同时又能让他们吃饱，所以这就是贪心的策略了

public int findContentChildren(int[] g, int[] s) {
    if (g.length == 0 || s.length == 0) {
        return 0;
    }
    Arrays.sort(g);
    Arrays.sort(s);
    int gIndex = 0;
    int sIndex = 0;
    while (gIndex < g.length && sIndex < s.length) {
        if (g[gIndex] <= s[sIndex]) {
            // g[gIndex]这个小孩获得饼干
            gIndex++;
        }
        sIndex++;
    }
    return gIndex;
}