You are given two integer arrays:
-
g: greed factors of children
-
s: sizes of available cookies
Each child can receive at most one cookie.
A child is satisfied only if they receive a cookie with size ≥ their greed factor.
Your task is to return the maximum number of satisfied children.
You must distribute cookies in a way that satisfies as many children as possible.
Key idea:
-
Sort both lists.
-
Give each child the smallest cookie that is large enough for them.
-
Move to the next child and cookie greedily.
An array g of greed values.
An array s of cookie sizes.
A single integer: the maximum number of satisfied children.
Example 1
Input:
g = [1,2,3]
s = [1,1]
Output:
1
Explanation:
Only one child can be satisfied because only one cookie meets or exceeds a child’s greed.
Example 2
Input:
g = [1,2]
s = [1,2,3]
Output:
2
Explanation:
Two children can be satisfied with cookie sizes 1 and 2 (or 1 and 3).
-
1 ≤ number of children ≤ 30,000
-
1 ≤ number of cookies ≤ 30,000
-
Greed values and cookie sizes are positive integers.
-
Sort greed values and cookie sizes.
-
Use two pointers to match children to cookies.
-
Always give the smallest suitable cookie.
After sorting, try to assign cookies from smallest to largest.
If a cookie can satisfy the current child, count it and move both pointers.
If not, try a larger cookie.
This ensures optimal matching.