Solution: Assign Cookies
Let's solve the Assign Cookies problem using the Greedy Techniques pattern.
We'll cover the following
Statement
You are given two integer arrays:
greedFactors
: This array represents the minimum cookie size required for each child to be content. Specifically,greedFactors[i]
denotes the minimum cookie size that childi
will accept to be satisfied.cookieSizes
: This array represents the sizes of the available cookies. For example,cookieSizes[j]
denotes the size of cookiej
.
Your objective is to distribute the cookies in a way that maximizes the number of content children. A child i
is content if they receive a cookie that is at least as large as their greed factor, i.e., cookieSizes[j] >= greedFactors[i]
. Each child can be assigned at most one cookie, which can only be given to one child.
Write an algorithm to maximize the number of children who can be content by assigning available cookies appropriately.
Constraints:
greedFactors.length
cookieSizes.length
greedFactors[i]
,cookieSizes[j]
Solution
We solve this problem efficiently using a greedy approach. The key is to assign each child the smallest cookie that satisfies their greed factor. First, the greed factors and cookie sizes are sorted in ascending order to ensure we can pair the least greedy child with the smallest possible cookie. The algorithm then uses two pointers: one for the children and one for the cookies. Starting with the least greedy child and the smallest cookie, it checks whether the current cookie can satisfy the child. If it can, both pointers are moved to the next child and cookie; if not, only the cookie pointer advances to find a larger cookie. This process continues until all children have been satisfied or all cookies have been used, maximizing the number of children who can be content.
The steps of the algorithm are as follows:
Sort the
greedFactors
of the children and thecookieSizes
in ascending order.Use two pointers,
currentChild
andcurrentCookie
, to track the current child and current cookie, respectively. Additionally, initialize a variablecontentChildren
to count how many children are satisfied.Iterate through both lists using a loop, which will continue as long as there are children and cookies left to consider (
currentChild < len(greedFactors)
andcurrentCookie < len(cookieSizes)
).Check if the current cookie can satisfy the current child:
If the current cookie (
cookieSizes[currentCookie]
) is large enough to satisfy the current child’s greed factor (greedFactors[currentChild]
), incrementcontentChildren
and move both pointers to the next child and the next cookie (currentChild++
andcurrentCookie++
).If the current cookie is not large enough to satisfy the child, move the cookie pointer only to try the next larger cookie (
currentCookie++
) while considering the same child.
Return the total number of content children once the loop finishes.
Let’s look at the following illustration to get a better understanding of the solution:
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.