Assign cookies
Satisfy the least greedy child with the smallest sufficient cookie. About 8 minutes.
The cookie assignment problem
Imagine handing out cookies at a party. Each child has a greed factor: the smallest cookie that will make them happy. Each cookie has a size. A child is content if their cookie is at least as big as their greed. Each child gets at most one cookie, and you want as many content children as possible.
- content
- 1
Smallest cookie (1) against the least greedy child (1): 1 ≥ 1, content. Move on to the next child and the next cookie.
Two pointers after sorting
Start with a marker on the least greedy child and another on the smallest cookie. If the cookie satisfies the child, that child is content and both markers move on.
If it doesn't, this cookie is too small for every other child too, since they are even greedier, so move only the cookie marker to try a bigger one.
g.sort()
s.sort()
child, cookie = 0, 0
while child < len(g) and cookie < len(s):
if s[cookie] >= g[child]:
child += 1
cookie += 1
return childChildren g = [1, 2, 3] and cookies s = [1, 1]. How many children can be satisfied?
- A1 child
- B2 children
Show the answer
1 child. Cookie 1 satisfies child 1. The remaining cookie 1 cannot satisfy child 2 or child 3.
Assign cookies
Assume you are an awesome parent and want to give your children some cookies. Each child i has a greed factor g[i], which is the minimum size of a cookie that the child will be content with; each cookie j has a size s[j]. If s[j] ≥ g[i], we can assign cookie j to child i. Your goal is to maximize the number of content children and return that maximum count. Each child can receive at most one cookie.
g = [1, 2, 3], s = [1, 1] → 1
1 ≤ g.length, s.length ≤ 100,000 · 1 ≤ g[i], s[j] ≤ 1,000,000,000