Assign Cookies

Problem

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 g[i], which is the minimum size of a cookie that the child will be content with; and each cookie j has a size s[j]. If s[j] >= g[i], 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.

Constraints

• 1 <= g.length <= 3 * 104
• 0 <= s.length <= 3 * 104
• 1 <= g[i], s[j] <= 231 - 1

Solution

The problem Assign Cookies can be solved by sorting both given vectors and assigning smallest possible s[j] for each g[i] where s[j] >= g[i].

Implementation

class Solution
{
  public:
    int findContentChildren(vector<int> &g, vector<int> &s)
    {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());

        int ret = 0;
        for (int idx1 = 0, idx2 = 0; idx1 < g.size() && idx2 < s.size(); idx2++)
            if (g[idx1] <= s[idx2])
            {
                idx1 += 1;
                ret += 1;
            }

        return ret;
    }
};