Arrays.sort(g);
Arrays.sort(s);
int i = 0;
for(int j=0;i<g.length && j<s.length;j++) {
if(g[i]<=s[j]) i++;
}
return i;
Just assign the cookies starting from the child with less greediness to maximize the number of happy children .
@fabrizio3 what about this?
[5, 9]
[4, 5, 5]
edited:
sorry I miss this "You cannot assign more than one cookie to one child".
@fabrizio3 Sorry, but this fails on the test-case:
g: [7,8,9,10]
s: [5,6,7,8]
Since we are comparing the elements in order, the 'g' values 7 and 8 would not be checked against those for 's' leading to an incorrect output of '0' (while the right answer would be '2').
@BatCoder said in Simple Greedy Java Solution:
g: [7,8,9,10]
s: [5,6,7,8]
in this case, when j at 0 and 1, i still remains at 0. The loop only increases j but not i.
When j at 2, i will increase to 1 because s[2] = 7 and g[0] = 7.
@BatCoder since i only moves back one index when gi <= sj, so when g is 7, the s will be 7 and then g 8 will compare with s 8. It will not fail.
Here's a slightly more readable version:
public class Solution {
public int findContentChildren(int[] children, int[] cookies) {
Arrays.sort(children);
Arrays.sort(cookies);
int child = 0;
for (int cookie = 0; child < children.length && cookie < cookies.length; cookie ++) {
if (cookies[cookie] >= children[child]) {
child ++;
}
}
return child;
}
}
@linmumu The answer should be 1, because it is said in the note that "You cannot assign more than one cookie to one child".
@lawonga best is to check with interviewer and ask if they want you to implement a sorting technique. most likely they would say no in which case you should be able to blurt out the efficient sorting techniques you could use eg: Arrays.sort uses quick sort underneath.