題目

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.

Example 1:
Input: [1,2,3], [1,1]
Output: 1
Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3. 
And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.
You need to output 1.

Example 2:
Input: [1,2], [1,2,3]
Output: 2
Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2. 
You have 3 cookies and their sizes are big enough to gratify all of the children, 
You need to output 2.

解析

題目中要求更多的分配cookies，即“貪心”。實現(xiàn)的思路比較簡單，根據(jù)題目中的邏輯進行實現(xiàn)即可，即從左至右遍歷s，如果比g大，即滿足該child。

實現(xiàn)（C語言）

int comp(const void* a, const void* b) {
    return *(int*)a > *(int*)b;
}

int findContentChildren(int* g, int gSize, int* s, int sSize) {
    qsort(g, gSize, sizeof(int), comp);
    qsort(s, sSize, sizeof(int), comp);
    
    int count = 0, j = 0;
    
    for (int i = 0; i < sSize; ++i) {
        if (s[i] >= g[j]) {
            ++count;
            ++j;
            
            if (j >= gSize)
                break;
        }
    }
    
    return count;
}

實現(xiàn)中使用到了qsort庫函數(shù)，即將數(shù)組進行從大到小排序，先從大到小進行滿足，可以更多的滿足child，這個是顯然的。