Greedy - 455. Distribute cookies

1 Title Description

455. Distribute cookies
     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 .

2 Title Example

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.

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/assign-cookies

3 Topic tips

1 <= g.length <= 3 * 10⁴
0 <= s.length <= 3 * 10⁴
1 <= g[i], s[j] <= 2³¹ - 1

4 Ideas

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 g1 To gm, Yes n A biscuit , The dimensions are s1 To sn, Satisfy gi≤gi+1 and sj≤sj+1, among 1≤i<m,1≤j<n.

Assume before i to 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 sj Is the rest of the biscuits to meet gi≤sj 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 gi+1≤sj 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 gi+1≤sj 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 gi+1 > 8j 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 , Maybe even because there is less — Fewer children are satisfied with a usable cookie .

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 à and j All for 0, Do the following .
For each element g Same as , The smallest not found or used j bring g[i]≤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 the sum of two arrays — At the end of traversal , 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 .

Complexity analysis
Time complexity :O(m log m + n log n), 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 logn).
· 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 .

5 My answer

class Solution {
    
    public int findContentChildren(int[] g, int[] s) {
    
        Arrays.sort(g);
        Arrays.sort(s);
        int numOfChildren = g.length, numOfCookies = s.length;
        int count = 0;
        for (int i = 0, j = 0; i < numOfChildren && j < numOfCookies; i++, j++) {
    
            while (j < numOfCookies && g[i] > s[j]) {
    
                j++;
            }
            if (j < numOfCookies) {
    
                count++;
            }
        }
        return count;
    }
}