Assign Cookies

The key idea

Sort both arrays, then walk them with two pointers. Give each child the SMALLEST cookie that is still big enough. Spending a large cookie on a low-greed child wastes it, so always satisfy the least greedy remaining child first with the smallest sufficient cookie.

Problem

You are the parent of children and want to give each one at most one cookie. Each child i has a greed factor g[i], the minimum size of a cookie that will content that child. Each cookie j has a size s[j]. If s[j] >= g[i], cookie j can be assigned to child i, and the child will be content. Your goal is to assign cookies so that the number of content children is the maximum, and return that count.

Constraints

1 <= g.length <= 3 * 10^4
0 <= s.length <= 3 * 10^4
1 <= g[i], s[j] <= 2^31 - 1

Examples

Input: g = [1,2,3], s = [1,1] Output: 1

Input: g = [1,2], s = [1,2,3] Output: 2

Complexity

Time: O(n log n + m log m) Space: O(1)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →