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.

Best match: give each child the smallest cookie that satisfies them.

Sort first: sort both the children and the cookies, smallest first.

Greed g = [1, 2, 3], cookies s = [1, 1], both sorted

child

content: 1

Smallest cookie (1) against the least greedy child (1): 1 ≥ 1, content. Move on to the next child and the next cookie.

Move 1 of 3

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.

Satisfied: move both markers on.

Too small: move only the cookie marker.

In code

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 child