Each child wants a cookie at least as big as their greed. Sort both lists and walk the cookies smallest first, handing each to the least greedy child it can satisfy, so no big cookie is wasted, in O(n log n + m log m).
▼The problem
LeetCode 455 (Easy). Child i has a greed factor g[i], the smallest cookie size that makes them content; cookie j has size s[j]. Each child gets at most one cookie, and child i is content if their cookie has size >= g[i]. Return the most children that can be made content.
Examples (LeetCode's): g = [1, 2, 3], s = [1, 1] → 1 (one size-1 cookie feeds greed 1; the other is too small for 2 or 3); g = [1, 2], s = [1, 2, 3] → 2.
The solution
def findContentChildren(g, s):
g.sort()
s.sort()
i = 0
for size in s:
if i < len(g) and size >= g[i]:
i += 1
return iTranscript
Assign Cookies. Each child has a greed factor: the smallest cookie that makes them content. Each child gets at most one cookie. Make as many children content as possible.
Take greeds one, two, three, and two cookies of size one. Only the first child can be satisfied: one. With greeds one and two, and cookies one, two, three, both children are content: two.
The naive way tries every way of handing out the cookies. Ten cookies alone have over three million orders.
The key idea: sort the children by greed and the cookies by size. Take the smallest cookie. If it satisfies the least greedy waiting child, give it. If not, skip it: every child left is greedier. Never spend a big cookie on a small appetite; swapping in the smaller one never hurts.
In code, sort both lists and point at the next hungry child. For each cookie, smallest first, if it's big enough, feed that child and move the pointer. The pointer ends on the answer.
A bigger example. Greeds two, three, one, two. Cookies one, four, one, two. Sorted: children one, two, two, three; cookies one, one, two, four. Cookie one feeds greed one. The next one is too small for greed two: skip. Cookie two feeds a two. Cookie four feeds the other two. Greed three still waits, but the cookies are gone. Three content children.
Sorting costs n log n plus m log m, and the walk is linear. Beyond the sort, just two counters.
Sort both, smallest cookie first, feed or skip. That's Assign Cookies.