LeetCode topic link:/problems/assign-cookies/description/
title narrative
Let's say you are an awesome parent and want to give your kids some small cookies. However, you can only give a maximum of one cookie per child.
For each child i, there is an appetite value g[i], which is the minimum size of a cookie that will satisfy the child's appetite; and for each cookie j, there is a size s[j]. If s[j] >= g[i], we can assign this cookie j to child i , and that child will be satisfied. Your goal is to satisfy as many number of children as possible and output this maximum value.
Example 1.
Inputs: g = [1,2,3], s = [1,1]
Output: 1
Explanation.
You have three children and two small cookies, and the appetite values of the 3 children are: 1,2,3.
Although you have two small cookies, since they are both size 1, you can only satisfy the child whose appetite value is 1.
So you should output 1.
Example 2.
Inputs: g = [1,2], s = [1,2,3]
Outputs: 2
Explanation.
You have 2 children and 3 small cookies, and the appetite values of the 2 children are 1,2.
You have more than enough cookies and sizes to satisfy all the kids.
So you should output 2.
Tip:
1 <= <= 3 * 10^4
0 <= <= 3 * 10^4
1 <= g[i], s[j] <= 2^31 - 1
Thoughts:
We can use a greedy strategy for this question, we have to satisfy as many children as possible in each step if we want to satisfy a large enough number of children, we can take small cookies to satisfy children with small appetites as much as possible, so that we reach a local optimum and a global
Optimality is about satisfying as many children as possible, so we should first sort this array of appetites and the array of cookies.
Then start with small cookies and try to satisfy kids with small appetites
Code:
class Solution {
public.
int findContentChildren(vector<int>& g, vector<int>& s) {
sort((), ()).
sort((), ());
// As a subscript to the appetites array, the final index is the number of children's appetites satisfied
int index = 0; for (int i = 0; i
for (int i = 0; i < (); i++) {
//Index should be less than the number of children, and update the index of the subscript when the cookie is greater than or equal to the appetite.
if (index < () && s[i] >= g[index]) index++;
}
// the final value of index is the number of children satisfied
return index.
}
};
Option 2
In fact, we could also go in the opposite direction and satisfy a child with a large appetite with a large cookie while using a variableresultto represent the result, but this time we're not traversing the cookie array, we're traversing the children array.
The code is as follows:
class Solution {
public.
int findContentChildren(vector<int>& g, vector<int>& s) {
// Sort the array
sort((), ()).
sort((), ());
// as the subscript of the cookie array
int index = () - 1;
// used to store the result
int result = 0; //Iterate through the array of cookies.
// Iterate through the cookie array, trying to satisfy children with large appetites with large cookies
for (int i = () - 1; i >= 0; i--) {
// Be sure to determine if index >= 0 first. otherwise some cases will runtime error
if (index >= 0 && g[i] <= s[index]) {
result++;
index--;;
}
}
// The value of result at the end is the result we asked for
return result; }
}
}; }