Assign Cookies
Maximum number of content children given sorted greed factors and cookie sizes — two-pointer greedy.
3 min read
greedy sorting two-pointers
Problem#
Child i is content if you give them a cookie of size ≥ g[i]. Each child gets at most one cookie, each cookie used at most once. Maximize content children.
Examples#
g = [1,2,3], s = [1,1]→1g = [1,2], s = [1,2,3]→2
Constraints#
1 <= n, m <= 3 * 10^4.
Approach#
Sort both ascending. Pointer i over greed, j over cookies. For each cookie, if s[j] >= g[i] it satisfies child i → advance both, count one. Else advance only j (cookie too small for this child).
Solution#
class Solution {public: int findContentChildren(vector<int>& g, vector<int>& s) { sort(g.begin(), g.end()); sort(s.begin(), s.end()); int i = 0, j = 0, count = 0; while (i < (int)g.size() && j < (int)s.size()) { if (s[j] >= g[i]) { ++i; ++count; } ++j; } return count; }};func findContentChildren(g []int, s []int) int { sort.Ints(g) sort.Ints(s) i, j, count := 0, 0, 0 for i < len(g) && j < len(s) { if s[j] >= g[i] { i++ count++ } j++ } return count}from typing import List
class Solution: def findContentChildren(self, g: List[int], s: List[int]) -> int: g.sort() s.sort() i = j = count = 0 while i < len(g) and j < len(s): if s[j] >= g[i]: i += 1 count += 1 j += 1 return countvar findContentChildren = function(g, s) { g.sort((a, b) => a - b); s.sort((a, b) => a - b); let i = 0, j = 0, count = 0; while (i < g.length && j < s.length) { if (s[j] >= g[i]) { i++; count++; } j++; } return count;};class Solution { public int findContentChildren(int[] g, int[] s) { Arrays.sort(g); Arrays.sort(s); int i = 0, j = 0, count = 0; while (i < g.length && j < s.length) { if (s[j] >= g[i]) { i++; count++; } j++; } return count; }}function findContentChildren(g: number[], s: number[]): number { g.sort((a, b) => a - b); s.sort((a, b) => a - b); let i = 0, j = 0, count = 0; while (i < g.length && j < s.length) { if (s[j] >= g[i]) { i++; count++; } j++; } return count;}Editorial#
Greedy works because matching the smallest possible cookie to the least-greedy unsatisfied child never wastes a cookie. Any other assignment can be rewritten in this order without losing any matches.
Complexity#
- Time: O(n log n + m log m).
- Space: O(1).
Concept revision#
Related#