We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Assign Cookies

Difficulty: Easy

Problem Description

You are tasked with distributing cookies to children based on their greed factors. Each child has a minimum cookie size they are content with, and each cookie has a size. The goal is to maximize the number of children who are content by assigning cookies to them.

Key Insights

  • Each child can only receive one cookie.
  • A child is content if the cookie size is greater than or equal to their greed factor.
  • To maximize the number of content children, we can use a greedy approach by sorting both arrays of greed factors and cookie sizes.

Space and Time Complexity

Time Complexity: O(n log n + m log m), where n is the number of children, and m is the number of cookies (due to sorting). Space Complexity: O(1), as we are using a constant amount of space apart from the input arrays.

Solution

The solution involves a greedy algorithm that sorts both the greed factors and cookie sizes in ascending order. By iterating through both arrays, we assign cookies to children when possible. If a cookie can satisfy a child's greed factor, we move to the next child. Otherwise, we move to the next cookie. This ensures that we maximize the number of content children.

Code Solutions

def findContentChildren(g, s):
    g.sort()  # Sort the greed factors
    s.sort()  # Sort the cookie sizes
    child_i = 0  # Pointer for children
    cookie_i = 0  # Pointer for cookies
    while child_i < len(g) and cookie_i < len(s):
        if s[cookie_i] >= g[child_i]:  # If the cookie can satisfy the child
            child_i += 1  # Move to the next child
        cookie_i += 1  # Always move to the next cookie
    return child_i  # Number of content children
← Back to All Questions