Skip to main content

Cookie distribution


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 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:

  1. Sort g (children greed) in non-decreasing order.

  2. Sort s (cookie sizes) in non-decreasing order.

  3. Use two pointers:

    • i over children (starting from least greedy).

    • j over cookies (starting from smallest).

  4. 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++).

  5. 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