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.

Example 1:
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.
Example 2:
Input: [1,2], [1,2,3]

Output: 2

Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2.
You have 3 cookies and their sizes are big enough to gratify all of the children,
You need to output 2.

题解：

分糖果，给出一些孩子对糖果的需求，存入g；糖果的大小，存入s；求糖果所能满足的孩子需求的最多的数量。
考虑贪心的思想（选取当前最优的策略的算法），以Input: [3,1,2], [4,1]为例：孩子对糖果的需求分别为1，2，3；糖果大小为1，1；

1. 分别对g和s中的元素进行排序，Input变为 [1,2,3], [1,4]；
2. 依次将g, s中的元素进行对比，让最小的糖果尽可能的满足需求小的孩子，这样当孩子或者糖果中的一个比较完成后，输出满足分配条件的孩子数量。

My Solution（C/C++完整实现）：

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int findContentChildren(vector<int> &g, vector<int> &s) {  //需求因子g, 糖果大小s
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int child = 0;
        int cookie = 0;
        while (child < g.size() && cookie < s.size()) {
            if (g[child] <= s[cookie]) {
                child += 1;
            }
            cookie += 1;
        }
        return child;
    }
};

int main() {
    Solution s;
    vector<int> children;
    vector<int> cookie;
    children.push_back(1);
    children.push_back(2);
    children.push_back(3);
    cookie.push_back(1);
    cookie.push_back(1);
    printf("%d\n", s.findContentChildren(children, cookie));
    return 0;
}

结果：

1

My Solution（Python）:

class Solution:
    def findContentChildren(self, g, s):
        """
        :type g: List[int]
        :type s: List[int]
        :rtype: int
        """
        g.sort()
        s.sort()
        child = cookie = result = 0
        while cookie < len(s) and child < len(g):
            if g[child] <= s[cookie]:
                result += 1
                child += 1
            cookie += 1
        return result

Reference:

class Solution:
    def findContentChildren(self, g, s):
        """
        :type g: List[int]
        :type s: List[int]
        :rtype: int
        """
        res = 0
        heapq.heapify(g)
        s.sort()
        for num in s:
            if not g:
                break
            elif g[0] <= num:
                res += 1
                heapq.heappop(g)
        return res