Assign Cookies
Problem
Each child i has greed g[i] and each cookie j has size s[j]. Cookie j can content child i if s[j] ≥ g[i]. Return the maximum number of content children.
g = [1, 2, 3], s = [1, 1]1def find_content_children(g, s):
g.sort(); s.sort()
i = j = 0
while i < len(g) and j < len(s):
if s[j] >= g[i]: i += 1
j += 1
return ifunction findContentChildren(g, s) {
g.sort((a, b) => a - b);
s.sort((a, b) => a - b);
let i = 0, j = 0;
while (i < g.length && j < s.length) {
if (s[j] >= g[i]) i++;
j++;
}
return i;
}class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g); Arrays.sort(s);
int i = 0, j = 0;
while (i < g.length && j < s.length) {
if (s[j] >= g[i]) i++;
j++;
}
return i;
}
}int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int i = 0, j = 0;
while (i < (int)g.size() && j < (int)s.size()) {
if (s[j] >= g[i]) i++;
j++;
}
return i;
}Explanation
The greedy idea is to never waste a big cookie on a low-greed child. If we sort both lists, we can hand the smallest cookie to the least greedy child it can satisfy, and that choice is always safe.
After sorting g (greed) and s (cookies), we sweep with two pointers: i over children and j over cookies. We always advance the cookie pointer j; we only advance the child pointer i when the current cookie is big enough (s[j] >= g[i]).
Why this works: if the current cookie cannot please the least greedy unsatisfied child, it cannot please anyone harder either, so we simply discard it and try the next, larger cookie. Every satisfied child increments i, and that final i is the count of content children.
Example: g = [1, 2, 3], s = [1, 1]. Cookie 1 satisfies child with greed 1 (i becomes 1). The next cookie 1 is too small for greed 2, so it is discarded. We run out of cookies with i = 1, so the answer is 1.