Assign Cookies

Easy· Sorting· Two Pointers

Problem

Each child i is content only with a cookie of size at least g[i], and each cookie j has size s[j]. Every child gets at most one cookie. Return the maximum number of children you can make content.

Examples

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

Output: 1

Both cookies have size 1, which only satisfies the first child.

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

Output: 2

Constraints

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

Hints & approach

Hint 1

Wasting a big cookie on an easily pleased child can cost you later.

Hint 2

Sort both arrays and try to satisfy the least greedy child with the smallest cookie that works.

Approachtry the hints first

Sort greed factors and cookie sizes ascending. Walk through the cookies with one pointer into the children: whenever the current cookie satisfies the current child, count a match and move to the next child; otherwise discard the cookie as too small for anyone remaining. Pairing smallest-sufficient cookie with least greedy child never blocks a better assignment.

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

Next →Lemonade Change