Easy · Sorted Greedy Matching
Understand → Visualise → Practice.
Each child needs a minimum cookie size. Assign at most one cookie per child and return the maximum satisfied children.
Sort both lists. Walking cookies from small to large, give the current cookie to the least greedy unsatisfied child if it is big enough. Small cookies are never wasted on children who could take a bigger one.
Sort greed factors and cookie sizes in ascending order.
For each cookie, if it is at least the current child's greed, that child is satisfied and you move to the next child.
The child pointer's final position is the answer.
O(n log n + m log m) time for sorting and O(1) extra space.
Giving the biggest cookie to the greediest child first can leave smaller children unfed when a smaller cookie would have done.
Read the full guide first: Greedy Algorithms and Interval Patterns.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.