Hand Out Cookies

EasyGreedy#greedy#sorting#two-pointers~15m

Problem

Each child has a smallest cookie size that will make them happy, and each cookie has a size. A child gets at most one cookie and a cookie goes to at most one child. Return the largest number of children you can make happy.

Examples

Input:  wants = [1, 2, 3], sizes = [1, 1]
Output: 1
Why:    both cookies only satisfy the child who wants size 1

Input:  wants = [1, 2], sizes = [1, 2, 3]
Output: 2

Input:  wants = [5], sizes = []
Output: 0
Why:    edge case, no cookies means no happy children

Hints

0 / 3

Solution

After sorting, the least demanding waiting child is the one most worth serving, and the smallest cookie that satisfies them is the one whose use costs the least; an exchange argument shows that swapping any optimal assignment towards this choice never loses a happy child. A cookie too small for the least demanding waiting child is too small for everyone after them too, so it is discarded. One pass over the cookies with a pointer into the children does the rest. Time is O(n log n + m log m) for the sorts, and space is O(1) beyond them.

def happy_children(wants, sizes):
    wants, sizes = sorted(wants), sorted(sizes)
    child = 0                                  # least demanding child still waiting
    for s in sizes:                            # smallest cookie first
        if child < len(wants) and s >= wants[child]:
            child += 1                         # this cookie is enough, hand it over
    return child

print(happy_children([1, 2, 3], [1, 1]))     # -> 1
print(happy_children([1, 2], [1, 2, 3]))     # -> 2
print(happy_children([5], []))               # -> 0

Python · runs in your browser

Stuck on the idea rather than the code? What Makes Greedy Work covers it.