Cookie Distribution
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
You are handing out cookies to children. Child i is satisfied only by a cookie of size at least greed[i], and cookie j
has size cookies[j]. Each child gets at most one cookie and each cookie goes to at most one child; leftover cookies and
children without a cookie are fine.
Return the maximum number of satisfied children.
Examples
| greed | cookies | result |
|---|---|---|
[1, 2, 3] | [1, 1] | 1 |
[1, 2] | [1, 2, 3] | 2 |
[5, 10, 2, 8] | [3, 9, 6, 1, 4] | 3 |
Example 3 — give cookies 3, 6, 9 to the children with greed 2, 5, 8. No cookie can satisfy the child with greed 10.
Efficiency
This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.
Function signature
solution(greed: int[], cookies: int[]) → int
Constraints
-
greed.length -
cookies.length -
greed[i],cookies[j]
Expected complexity
- Time
- O(N log N + M log M)
- Space
- O(1)
Examples
| greed | cookies | Expected |
|---|---|---|
[1,2,3] | [1,1] | 1 |
[1,2] | [1,2,3] | 2 |
[5,10,2,8] | [3,9,6,1,4] | 3 |
Hint
Hint
Serve the least greedy child first with the smallest cookie that satisfies them; bigger cookies are saved for greedier children. Sort both arrays and walk the cookies from small to large with a pointer into the children (two pointers). Rescanning the cookies for every child is and exceeds the time limit; sorting plus one pass is .
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | estimated |
| C++ (GCC, gnu++23) | 200 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1404 ms | derived |
| Kotlin 2.4 (JVM) | 1400 ms | estimated |
| C# 14 (.NET 10) | 1400 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 11 | verdict only |
| performance | 60 | 3 | verdict only |