一. 贪心基础 Assign Cookies
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i ，都有一个胃口值 g(i) ，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j ，都有一个尺寸 s(j) 。如果 s(j) >= g(i) ，我们可以将这个饼干 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.
解决思路
先把饼干按大小排序, 小朋友按胃口大小排序
如果最大的饼干能满足胃口最大的小朋友， 就把最大的饼干给他,
否则就把最大的饼干给胃口第二大的小朋友....以此类推

代码
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/// 455. Assign Cookies
/// https://leetcode.com/problems/assign-cookies/description/
/// 先尝试满足最贪心的小朋友
/// 时间复杂度: O(nlogn)    主要体现在排序中
/// 空间复杂度: O(1)
class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        // s表示饼干   g表示小朋友
        sort(g.begin(), g.end(), greater<int>()); // 从大到小排序, greater表示从大到小, 否则默认从小到大
        sort(s.begin(), s.end(), greater<int>());

        int gi = 0, si = 0;
        int res = 0;
        while(gi < g.size() && si < s.size()){
            if(s[si] >= g[gi]){
                res ++;
                si ++;
                gi ++;
            }
            else
                gi ++;
        }

        return res;
    }
};
二. 贪心算法和动态规划的关系 Non-overiapping Intervals
给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。  

注意:

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

输入: [ [1,2], [2,3], [3,4], [1,3] ]

输出: 1

解释: 移除 [1,3] 后，剩下的区间没有重叠。
示例 2:

输入: [ [1,2], [1,2], [1,2] ]

输出: 2

解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
示例 3:

输入: [ [1,2], [2,3] ]

输出: 0

解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
解题思路
暴力解法: 先要排序, 方便判断不重叠,找出所有子区间的组合, 之后判断它不重叠。 O((2^n)*n)  

动态规划: 先要排序, 方便判断不重叠,使用最长上升子序列 的解法
动态规划代码
#include <iostream>
#include <vector>

using namespace std;


/// Definition for an interval.
struct Interval {
    int start;
    int end;
    Interval() : start(0), end(0) {}
    Interval(int s, int e) : start(s), end(e) {}
};

bool compare(const Interval &a, const Interval &b){

    if(a.start != b.start)
        return a.start < b.start;
    return a.end < b.end;
}

/// 435. Non-overlapping Intervals
/// https://leetcode.com/problems/no ... ervals/description/
/// 动态规划
/// 时间复杂度: O(n^2)
/// 空间复杂度: O(n)
class Solution {

public:
    int eraseOverlapIntervals(vector<Interval>& intervals) {

        if(intervals.size() == 0)
            return 0;

        sort(intervals.begin(), intervals.end(), compare);

        // memo表示以intervals为结尾的区间能构成的最长不重叠区间序列 个数, 开始时 都为1
        vector<int> memo(intervals.size(), 1);
        for(int i = 1 ; i < intervals.size() ; i ++)
            // memo
            for(int j = 0 ; j < i ; j ++) // 扫描i前面的 所有区间
                if(intervals.start >= intervals[j].end) // 满足条件, 则计算 到第i个区间时, 可以连起来的区间数
                    memo = max(memo, 1 + memo[j]);

        int res = 0;
        for(int i = 0; i < memo.size() ; i ++)
            res = max(res, memo);

        return intervals.size() - res; // 得到要去除的 最少区间数
    }
};
贪心算法
按照区间的结尾排序,
每次选择结尾最早的, 且和前一个区间不重叠的区间
代码

#include <iostream>
#include <vector>

using namespace std;


/// Definition for an interval.
struct Interval {
    int start;
    int end;
    Interval() : start(0), end(0) {}
    Interval(int s, int e) : start(s), end(e) {}
};

bool compare(const Interval &a, const Interval &b){  // 结尾早的排前面, 结尾一样 选区间长的排前面
    if(a.end != b.end)
        return a.end < b.end;
    return a.start < b.start;
}

/// 435. Non-overlapping Intervals
/// https://leetcode.com/problems/no ... ervals/description/
/// 贪心算法
/// 时间复杂度: O(n)
/// 空间复杂度: O(n)
class Solution {
public:
    int eraseOverlapIntervals(vector<Interval>& intervals) {

        if(intervals.size() == 0)
            return 0;

        sort(intervals.begin(), intervals.end(), compare);

        int res = 1;  // 当前可以保留的 区间数
        int pre = 0;
        for(int i = 1 ; i < intervals.size() ; i ++)
            if(intervals.start >= intervals[pre].end){
                res ++;
                pre = i;
            }

        return intervals.size() - res;
    }
};
三. 贪心选择性质的证明
一般过程如下：
假设贪心算法为A 不是最优解,
则存在一个最优算法O

只要证明A完全可以代替O，且不影响求出最优解 即可
上一节中贪心选择性质的证明
题目: 给定一组区间, 问最多保留多少个区间, 可以让这些区间之间相互不重叠。

贪心算法: 按照区间的结尾排序, 每次选择结尾最早的, 且和前一个区间不重叠的区间


反证法证明:

贪心算法的 某次选择的是[s(i), f(i)] 这个区间; 其中f(i)是当前所有选择中结尾最早的

假设这个选择不是最优解。 也就是说, 如果这个问题的最优解为k, 则这个问题得到的解, 最多为k-1


假设最优解在这一步选择的是[s(j), f(j)], f(j)>f(i)

显然 可以将[s(i),f(i)]替换[s(j),f(j)],  而不影响后序的区间选择：

    f(j)>f(i)  显然不会影响后面选择
    而s(i)和s(i), 则隐藏在条件中:
    前面的m次选择是一样的, 到这一次 使用'贪心选择'还是 '最优选择', 都不会对全面已经选择过的区间  产生影响了
---------------------

奈斯，加油