Sharing my C++ greedy solution using sorting and two pointers


  • 0
    C

    Idea is try to assign the biggest cookie to the greediest kid. So we sort the two inputs with descending order and use two pointers to go over the assignment.

    If cookie can meet the greedy factor, we assign this cookie, otherwise we skip this kid.

        int findContentChildren(vector<int>& g, vector<int>& s) {
            sort(g.begin(), g.end(), std::greater<int>());
            sort(s.begin(), s.end(), std::greater<int>());
            
            int count = 0;
            int sidx = 0;
            int gidx = 0;
            while (sidx < s.size() && gidx < g.size()) {
                if (g[gidx] <= s[sidx]) {
                    sidx++;
                    count++;
                }
                gidx++;
            }
            
            return count;
        }
    

Log in to reply
 

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