Assign Cookies
Easy · Greedy · Array · Two Pointers · Greedy · Sorting
Problem
You are handing out cookies to children. Child i has a greed factor g[i]: the smallest cookie size that will make them content. Cookie j has size s[j].
Each child gets at most one cookie, and each cookie goes to at most one child. Child i is content when the cookie they get has s[j] >= g[i]. Return the largest number of children you can make content.
Examples
Input: g = [1,2,3], s = [1,1] Output: 1
Both cookies have size 1. Only the child with greed 1 can be made content, and the other cookie fits nobody else.
Input: g = [1,2], s = [1,2,3] Output: 2
Size 1 goes to the child with greed 1 and size 2 to the child with greed 2. One cookie is left over.
Input: g = [3,1,2], s = [2,3] Output: 2
Give size 2 to greed 1 (or greed 2) and size 3 to greed 3. Giving size 3 to a child with greed 1 would leave nothing big enough for greed 3.
Constraints
- 1 <= len(g) <= 3 · 10^4
- 0 <= len(s) <= 3 · 10^4
- 1 <= g[i], s[j] <= 2^31 - 1
Approaches
- Baseline: scan for the smallest cookie that fits — time O(n · m), space O(m)
Follow-up
What if a child may receive several cookies whose sizes add up to their greed? Then it becomes a packing problem: no simple greedy is always right, and the general version is NP-hard. The one-cookie rule is what makes the sorted greedy exact.
Related problems
Start free on Cariara · Coding problems · System design studio
