Assign Cookies — Two-Pointer Greedy
Sanjeev SharmaAdvertisement
Problem
Children have greed factors g[i]; cookies have sizes s[j]. Assign each cookie to at most one child. Maximize satisfied children.
Approach — Sort + Two Pointers
Sort both. Try to satisfy least greedy child first with the smallest sufficient cookie.
Time: O(n log n) | Space: O(1)
Solutions
Python
class Solution:
def findContentChildren(self, g: list[int], s: list[int]) -> int:
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 i
C++
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;
while(i<g.size()&&j<s.size()){if(s[j]>=g[i])i++;j++;}
return i;
}
};
Complexity
- Time: O(n log n) | Space: O(1)
Advertisement
