LeetCode455. Assign Cookies（贪心）

Easy
Accepted：60,685
Submissions：125,878

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.

链接

https://leetcode.com/problems/assign-cookies

题意

假设你现在要给你的孩子们分一些饼干，每个孩子最多分一个。每个孩子都有一个贪婪指数gi，每块饼干有一个尺寸si，当si大于等于gi时，就可以把饼干分给孩子，孩子就会变得开心，问如何分配饼干让最多的孩子开心，输出最多孩子开心的数量。

题解

此时，一个表情包在我脑海中浮现，“懂不懂，这道题用贪心”。

我们要使得尽可能多的孩子开心，就是尽可能分配更多的饼干。考虑一个贪心策略：每次尽可能的先分配最大尺寸的饼干给贪婪指数最大的孩子，这样我们就可以获得一个最优解。

为了更好处理，我们可以对孩子的贪婪指数和饼干的尺寸从大到小排序，然后使用一个while循环。

因为要排序，所以时间复杂度为$O(nlogn)$，一个比较“暴力”的写法是两重循环。

代码

Runtime: 44 ms, faster than 74.03% of C++ online submissions for Assign Cookies.
Memory Usage: 10.4 MB, less than 76.00% of C++ online submissions for Assign Cookies.

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        int n = g.size(), m = s.size();
        sort(g.begin(), g.end(), greater <>()); // 从大到小排序
        sort(s.begin(), s.end(), greater <>());
        int ans = 0;
        int i = 0, j = 0;
        while (i < n && j < m)
        {
            if (s[j] >= g[i])
            {
                ++i, ++j;
                ++ans;
            }
            else
                ++i;
        }
        return ans;
    }
};

Runtime: 876 ms, faster than 5.04% of C++ online submissions for Assign Cookies.
Memory Usage: 10.1 MB, less than 100.00% of C++ online submissions for Assign Cookies.

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        int n = g.size(), m = s.size();
        vector<bool>vis(m + 1, false);
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int ans = 0;
        for (int i = n - 1; i >= 0; --i)
        {
            for (int j = m - 1; j >= 0; --j)
            {
                if (!vis[j] && s[j] >= g[i])
                {
                    ++ans;
                    vis[j] = true;
                    break;
                }
            }
        }
        return ans;
    }
};

The end.
2019年4月11日星期四