Simple Greedy Java Solution


  • 46
    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 .


  • 0
    I

    @fabrizio3 what about this?
    [5, 9]
    [4, 5, 5]

    edited:
    sorry I miss this "You cannot assign more than one cookie to one child".


  • 1
    S

    C++ Version
    int findContentChildren(vector<int>& g, vector<int>& s) {
    sort(g.begin(),g.end());
    sort(s.begin(),s.end());
    int m = g.size(), n = s.size(), i=0, j=0;
    for(; i<m && j<n; j++){
    if(g[i] <= s[j])i++;
    }
    return i;
    }


  • 1
    S

    one more judge.

        Arrays.sort(g);
        Arrays.sort(s);
        count = s.length-1;
        for(int i=g.length-1; i>=0; i--)
        	if(g[i] <= s[count])	{
        		re++;
        		count--;
        		if(count <0)
        			break;
        	}

  • -1
    B

    @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').


  • 0
    Z

    @abhishek_naik

    The solution passes this test-case though...


  • 0
    B

    @BatCoder But the greedy method works on your test case, both has answer of 2.


  • 0
    J

    @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.


  • 0
    J

    @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.


  • 0
    K

    @fabrizio3

    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;
        }
    }
    

  • 0
    G

    @fabrizio3 Good,learn a lot from your solution,thx, :)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.