DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Assign Cookies

easyGreedy

Problem statement

You have some children and some cookies. Child i has a greed factor g[i]: the smallest cookie size that will make them content. Cookie j has size s[j]. A child is content if they get one cookie whose size is at least their greed factor. Each child gets at most one cookie, and each cookie goes to at most one child.

Return the largest number of children you can make content.

Examples

Example 1

Input: g = [2, 5, 3], s = [3, 1, 2]

Output: 2

Explanation: Give the size-2 cookie to the child with greed 2 and the size-3 cookie to the child with greed 3. No cookie is big enough for the child with greed 5.

Example 2

Input: g = [4, 4], s = [1, 2]

Output: 0

Explanation: Every cookie is smaller than every child's greed factor.

Hints

Approach

Sort both lists and walk them together with two pointers.

  1. Sort g and s ascending. Let child = 0.
  2. Walk through the cookies from smallest to largest. If the current cookie satisfies g[child], give it to that child and move child forward.
  3. Otherwise skip the cookie: it is too small for this child, and every remaining child is at least as greedy.
  4. Stop when either list runs out. child is the answer.

Why greedy is safe: if the least greedy child can be satisfied at all, giving them the smallest cookie that works never hurts, because any larger cookie is at least as useful to someone else. After sorting, the walk itself is linear.

ComplexityTime O(n log n + m log m)Space O(1) extra (plus sort)
Python
class Solution:
def findContentChildren(self, g: list[int], s: list[int]) -> int:
g, s = sorted(g), sorted(s)
child = 0
for size in s:
if child == len(g):
break
if size >= g[child]: # smallest cookie that fits this child
child += 1
return child

Follow-up questions

  • Each cookie can be split between children. How does the problem change?
  • Return which cookie each child received, not just the count.

Frequently asked questions

Yes, as long as you mirror the rule: walk from the largest cookie down and give it to the greediest child it satisfies, skipping children who cannot be satisfied. Both directions reach the same count. What fails is matching in an arbitrary order.

It is a small bin-matching problem: fit workloads with a minimum resource request onto nodes or instances with fixed capacity, maximising how many workloads get placed. Sorting both sides and using the smallest resource that fits is the same best-fit idea schedulers use to avoid wasting large machines on small jobs.