Funcia
Lv.1greedysortingtwo-pointers

Cookie Distribution

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
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

greedcookiesresult
[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

  • 1≤1 \le greed.length ≤200,000\le 200{,}000
  • 1≤1 \le cookies.length ≤200,000\le 200{,}000
  • 1≤1 \le greed[i], cookies[j] ≤109\le 10^9

Expected complexity

Time
O(N log N + M log M)
Space
O(1)

Examples

greedcookiesExpected
[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 O(N⋅M)O(N \cdot M) and exceeds the time limit; sorting plus one pass is O(Nlog⁡N+Mlog⁡M)O(N \log N + M \log M).

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251404 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4011verdict only
performance603verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.