Leetcode（455）—— Distribute cookies

subject

Suppose you are a great parent , Want to give your kids some cookies . however , Each child can only give one biscuit at most .

For every child i, All have an appetite value g[i], This is the smallest size of biscuit that can satisfy children's appetite ; And every cookie j, They all come in one size s[j] . If s[j] >= g[i], We can put this biscuit j Assign to children i , The child will be satisfied . Your goal is to meet as many children as possible , And output the maximum value .

Example 1：

Input : g = [1,2,3], s = [1,1]
Output : 1
explain :
You have three children and two biscuits ,3 The appetites of a child are ：1,2,3.
Although you have two biscuits , Because they are all of the same size 1, You can only make your appetite worth 1 The children of .
So you should output 1.

Example 2：

Input : g = [1,2], s = [1,2,3]
Output : 2
explain :
You have two children and three biscuits ,2 The appetites of a child are 1,2.
You have enough cookies and sizes to satisfy all children .
So you should output 2.

Tips ：

• $1$ <= g.length <= $3\ast 10^4$
• $0$ <= s.length <= $3\ast 10^4$
• $1$ <= g[i], s[j] <= $2^{31-1}$

Answer key

Key points ： Think about the local optimum , Figure out the global optimum , It feels that the local optimum can deduce the global optimum , And can't think of a counterexample , Then try greed

Method 1 ： Sort + greedy

Ideas

​​   Because children with the least hunger are the most likely to be full , So let's think about this kid first . In order to try to make the rest of the biscuits satisfy the hungry children , So we should put more than or equal to this child's hunger degree 、 And the smallest biscuit for the child . After satisfying the child , We take the same strategy , Consider the least hungry child left , Until there are no biscuits that meet the conditions .

​​   In order to meet as many children as possible , From the perspective of greed , Each child should be satisfied in the order of their appetite from small to large , And for every child , Choose the smallest biscuit that meets the child's appetite . Prove the following .

​​   Suppose there is $m$ A child , The appetites are $g_1$ To $g_m$, Yes $n$ A biscuit , The dimensions are $s_1$ To $s_n$, Satisfy $g_i\le g_{i+1}$ and $s_j\le s_{j+1}$, among $1\le i<m$,$1\le j<n$.

Assume before $i-1$ After the first child distributed the biscuits , It can meet the requirements of $i$ The smallest biscuit for a child's appetite is the $j$ A biscuit , namely $s_j$ Is the rest of the biscuits to meet $g_i\le s_j$ The minimum value of , The optimal solution is to put the $j$ A biscuit is allocated to the $i$ A child . If not allocated in this way , Consider the following two scenarios ：

• If $i<m$ And $g_{i+1}\le s_j$ It was also established , Then if $j$ A biscuit is allocated to the $i+1$ A child , And there are still some biscuits left , Then you can put the second $j+1$ A biscuit is allocated to the $i$ A child , The result of distribution will not satisfy more children ;
• If $j<n$, Then if $j+1$ A biscuit is allocated to the $i$ A child , When $g_{i+1}\le s_j$ when , You can put the second $j$ A biscuit is allocated to the $i+1$ A child , The result of distribution will not satisfy more children ; When $g_{i+1}>s_j$ when , The first $j$ A biscuit cannot be assigned to any child , So there is one less available biscuit left , Therefore, the result of distribution will not allow more children to be satisfied , Even fewer children may be satisfied because of the lack of a usable biscuit .

​​   Based on the above analysis , You can use greedy methods to satisfy as many children as possible .

​​   First, the array $g$ and $s$ Sort , And then traverse from small to large $g$ Every element in , For each element, find a that satisfies that element $s$ The smallest element in . To be specific , Make $i$ yes $g$ The subscript ,$j$ yes $s$ The subscript , At the beginning $i$ and $j$ All for $0$, Do the following .

​​   For each element $g[i]$, find Unused The smallest $j$ bring $g[i]\le s[j]$, be $s[j]$ You can meet $g[i]$. because $g$ and $s$ It's in order , Therefore, the whole process only needs to compare the array $g$ and $s$ Traverse once each . When one of the two arrays ends , It means that all the children are assigned to biscuits , Or all the cookies have been distributed or tried to be distributed （ Maybe some cookies can't be distributed to any children ）, At this time, the number of children assigned to biscuits is the maximum number that can be met .

Code implementation

My own ：

class Solution {
    
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
    
        //  Ascending sort 
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());

        int n = 0;
        vector<int>::iterator p = s.begin();

        for(auto kid: g){
    
            while(p != s.end()){
    
                //  Judge whether this biscuit can make the child full 
                if(kid <= *p){
    
                    n++;
                    p++;
                    break;
                }else p++;
            }
            if(p == s.end()) break;
        }
        return n;
    }
};

Complexity analysis

Time complexity ：$O(mlogm+nlogn)$, among $m$ and $n$ They are arrays $g$ and $s$ The length of . The time complexity of sorting two arrays is $O(m\log m+n\log n)$, The time complexity of traversing an array is $O(m+n)$, So the total time complexity is $O(m\log m+n\log n)$.
Spatial complexity ：$O(\log m+\log n)$, among $m$ and $n$ They are arrays $g$ and $s$ The length of . The space complexity is mainly the extra space cost of sorting .