Graph Theory37 sections · 1633 units
Open in Course

Problem - Assign Cookies

(Greedy vs matching)

You have cookies with sizes and children with greed factors. Each child accepts a cookie if its size is at least their greed factor. Assign cookies to maximize the number of content children. Each cookie can be given to at most one child.

This can be solved greedily (sort both, assign smallest valid cookie) or as bipartite matching (children are LL, cookies are RR, edges when size \geq greed).