Code Implementation

class Solution:
    def findContentChildren(self, g, s):
        g.sort()
        s.sort()
        child = 0
        cookie = 0
        while child < len(g) and cookie < len(s):
            if s[cookie] >= g[child]:
                child += 1
            cookie += 1
        return child
      

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int child = 0, cookie = 0;
        while (child < g.size() && cookie < s.size()) {
            if (s[cookie] >= g[child]) {
                child++;
            }
            cookie++;
        }
        return child;
    }
};
      

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int child = 0, cookie = 0;
        while (child < g.length && cookie < s.length) {
            if (s[cookie] >= g[child]) {
                child++;
            }
            cookie++;
        }
        return child;
    }
}
      

var findContentChildren = function(g, s) {
    g.sort((a, b) => a - b);
    s.sort((a, b) => a - b);
    let child = 0, cookie = 0;
    while (child < g.length && cookie < s.length) {
        if (s[cookie] >= g[child]) {
            child++;
        }
        cookie++;
    }
    return child;
};
      

Problem Description

You are given two integer arrays: g (children's greed factors) and s (cookie sizes). Each child i has a greed factor g[i], which is the minimum size of a cookie that will satisfy them. Each cookie j has a size s[j]. Your task is to assign cookies to children so that the maximum number of children are content. Each child can receive at most one cookie, and each cookie can be assigned to at most one child. The goal is to return the maximum number of content children.

• Each child can get at most one cookie.
• Each cookie can be assigned to at most one child.
• You cannot reuse cookies or assign multiple cookies to the same child.
• There may not be enough cookies for all children.
• Return the maximum number of children that can be content.

Thought Process

At first glance, a brute-force approach might seem reasonable: try every possible way to assign cookies to children and count the number of content children for each configuration. However, this is highly inefficient, especially as the number of children and cookies increases.

To optimize, consider the nature of the problem: each child has a minimum requirement, and each cookie has a size. We want to use the smallest cookie possible to satisfy each child, so that larger cookies remain available for greedier children. This leads us to a greedy strategy: always try to satisfy the least greedy child with the smallest available cookie that is big enough.

By sorting both the greed factors and cookie sizes, and then assigning cookies in order, we can efficiently maximize the number of content children.

Solution Approach

The solution uses a greedy algorithm. Here are the steps:

1. Sort the g array (children's greed factors) in ascending order. This ensures we deal with the least greedy child first.
2. Sort the s array (cookie sizes) in ascending order. This allows us to use smaller cookies first, saving larger ones for greedier children.
3. Initialize two pointers: one for children (child) and one for cookies (cookie), both starting at 0.
4. While there are children and cookies left:
   • If the current cookie can satisfy the current child (s[cookie] >= g[child]), assign the cookie to the child and move both pointers forward.
   • If not, move only the cookie pointer forward to try the next larger cookie for the same child.
5. When either pointer reaches the end of its array, stop. The child pointer now indicates how many children have been contented.

This approach works because by always giving the smallest suitable cookie to the least greedy child, we leave larger cookies for children who need them, maximizing the total number of content children.

Example Walkthrough

Suppose g = [1, 2, 3] and s = [1, 1].

1. Sort both arrays (they are already sorted here): g = [1, 2, 3], s = [1, 1].
2. Initialize child = 0, cookie = 0.
3. Iteration 1:
   • g[0] = 1, s[0] = 1
   • s[0] >= g[0] (1 >= 1), so assign cookie 0 to child 0.
   • Increment both pointers: child = 1, cookie = 1.
4. Iteration 2:
   • g[1] = 2, s[1] = 1
   • s[1] < g[1] (1 < 2), so cookie 1 is too small. Increment cookie only: cookie = 2.
5. End:
   • No more cookies. Number of content children is child = 1.

Thus, only one child can be content with the available cookies.

Time and Space Complexity

• Brute-force approach:
  • Would involve trying all possible assignments, which is factorial time: O(m!), where m is the number of cookies. This is infeasible for large inputs.
• Optimized (greedy) approach:
  • Sorting g: O(n log n), where n is the number of children.
  • Sorting s: O(m log m), where m is the number of cookies.
  • The two-pointer assignment is O(n + m) since each pointer only moves forward.
  • Total time complexity: O(n log n + m log m)
  • Space complexity: O(1) extra space (if sorting in-place), otherwise O(n + m) if not.

Summary

The Assign Cookies problem is elegantly solved with a greedy algorithm: sort both arrays, then use a two-pointer approach to assign the smallest suitable cookie to each child. This ensures that more demanding children have a better chance of being satisfied, maximizing the number of content children. The approach is efficient, simple to implement, and leverages the power of sorting for optimal matching.