FXTi's blog
0%

assign-cookies

Posted on Edited on

Assign Cookies – LeetCode 455

Problem

Description

Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor gi, which is the minimum size of a cookie that the child will be content with; and each cookie j has a size sj. If sj >= gi, we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.

Note:
You may assume the greed factor is always positive.
You cannot assign more than one cookie to one child.

Answer

Original

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        unsigned result = 0;
        sort(g.begin(),g.end(),[](const int l, const int r) {return l > r;});
        sort(s.begin(),s.end(),[](const int l, const int r) {return l > r;});
        for(auto pg = g.cbegin(),ps = s.cbegin();pg != g.cend() && ps != s.cend(); ++pg){
            if(*ps >= *pg){
                ++result;
                ++ps;
            }   
        }
        return result;
    }
};

思路

优先排序，之后用贪心进行匹配。时间复杂度$O(log{n})$，空间复杂度$O(1)$。
耗时$41$ ms，排名$42.86\%$

Better

思路

还没看到更好的思路。