455. Assign Cookies 贪心算法

Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor gi, which is the minimum size of a cookie that the child will be content with; and each cookie j has a size sj. If sj >= gi, we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.

Note:
You may assume the greed factor is always positive.
You cannot assign more than one cookie to one child.

Input: [1,2,3], [1,1]

Output: 1

Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3.
And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.
You need to output 1.

让我们使用贪心算法来解决它！贪心算法的核心思想是 坚持当下的最好选择 。那么在这道题中， 当下的最好选择 是什么？答案是，先将“较小的饼干”分给“对饼干尺寸要求最小”、“最好说话”的孩子，因为他们最容易满足，这样才能最大化满足孩子的数量。那么，整个分配流程就应该是这样的：

首先，将孩子们按“对饼干尺寸要求最小”排序，将饼干按尺寸大小排序。
然后，判断第一块饼干是否能满足第一个孩子，能就分给他，否则就换个稍微大点的，直到满足这个孩子。
满足第一个孩子后，再对第二个、第三个以及后面的孩子重复上面一步，直到饼干分完为止。
最后统计满足了多少个孩子，并返回结果。

class Solution(object):
    def findContentChildren(self, g, s):
        """
        :type g: List[int]
        :type s: List[int]
        :rtype: int
        """
        if not g or not s :
            return 0
        g = sorted(g)
        s = sorted(s)
        gi = 0
        si = 0
        while gi < len(g) and si < len(s):
            if g[gi]<=s[si]:
                gi+=1
            si+=1
        return gi