Problem Summary
You have n children and m cookies.
Each child i has a greed factor g[i] (minimum cookie size needed to be happy).
Each cookie j has a size s[j].
Each child can receive at most one cookie, and each cookie can be used for at most one child.
A child is content if assigned_cookie_size >= greed_factor.
For each test case, you must compute the maximum number of content children.
Input:
T test cases.
For each test case:
Two integers n (children), m (cookies).
Array g of length n: greed factors.
Array s of length m: cookie sizes.
Output:
For each test case, a single integer: the maximum number of content children.
Constraints:
1 ≤ T ≤ 10
1 ≤ n ≤ 3×104
0 ≤ m ≤ 3×104
1 ≤ g[i],s[j] ≤ 231-1
Examples Explanation
Sample:
Input:
2
4 3
2 3 1 4
1 3 2
3 5
1 2 2
2 3 1 4 5
Output:
3
3
Test case 1:
Children greed: [2, 3, 1, 4]
Cookies: [1, 3, 2]
One optimal assignment:
cookie 1 → child with greed 1 (content)
cookie 2 → child with greed 2 (content)
cookie 3 → child with greed 3 (content)
Child with greed 4 cannot be satisfied (no cookie ≥ 4 left).
So answer = 3.
Test case 2:
Children greed: [1, 2, 2]
Cookies: [2, 3, 1, 4, 5]
One optimal assignment:
cookie 1 → child with greed 1
cookie 2 → child with greed 2
cookie 3 → child with greed 2
All 3 children are satisfied. Extra cookies are unused.
So answer = 3.
Approach
Pattern:
This is a classic greedy + two pointers problem.
Naive Idea (and why it’s suboptimal):
Naive approach:
For each child, try to find any cookie that can satisfy it (e.g., scan through all cookies).
Mark cookie as used when assigned.
This leads to:
Worst-case time: O(n×m), up to 9×108 operations, too slow.
Optimal Greedy Approach
High-Level Idea:
To maximize the number of content children:
It is optimal to give the smallest possible cookie that still satisfies a child.
Also, we should satisfy children in order of increasing greed.
So:
Sort g (children greed) in non-decreasing order.
Sort s (cookie sizes) in non-decreasing order.
Use two pointers:
i over children (starting from least greedy).
j over cookies (starting from smallest).
For each child in order:
If current cookie s[j] is big enough (s[j] >= g[i]): assign it, increment both i and j, and increase count.
Else: cookie is too small; move to next cookie (j++).
Stop when either we run out of children or cookies.
Key Observations:
Giving a big cookie to a child with small greed might waste that cookie, which could be needed for a more greedy child. The sorting + smallest-sufficient-cookie strategy avoids this waste.
Sorting ensures:
The least greedy children are satisfied first with the smallest cookies.
Bigger cookies are preserved for greedier children.
Edge Cases:
m = 0: no cookies, answer is 0.
n = 0: (not in constraints, but if it occurs) answer is 0.
All cookies smaller than all greed factors: answer 0.
More cookies than children: some cookies remain unused; answer ≤ n.
Pseudo-code:
Complexity Analysis:
Let n = number of children, m = number of cookies.
Sorting g: O(nlogn)
Sorting s: O(mlogm)
Two-pointer scan: O(n+m)
Time Complexity: O(nlogn+mlogm)
Space Complexity:
Sorting in-place: O(1) extra space (beyond input arrays) or O(n+m) if the language’s sort uses extra memory.
We don’t use additional large data structures.
Java code
C code
C++ code
Python code
JavaScript code






Comments
Post a Comment