455 Assign Cookies

1. 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 g[i], which is the minimum size of a cookie that the child will be content with; and each cookie j has a size s[j]. If s[j] >= g[i], 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.

constraints :

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

2. Algorithms

When we traverse two input list which length of each list is differnt, we need to connect index of two list with and. After that, we can stop when traversing one list is over.

 

Because our condition counting content children is s[j] >= g[i], we need to increment content children when condition fits.

1. Start
2. Declare two variables i, j, and content. Initialize them to 0.
3. Sort two input list.
4. Repeat the steps until i == length(g) and j == length(s).
   1. If s[j] is greater than and equal to g[i],
      1. Increment content by 1 and i by 1.
   2. Increment j by 1.
5. Return the value of content out of loop.
6. End

3. Codes

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        # i : i will tarverse index of g. 
        # j : j will traverse index of s. 
        # content : res will store the number of content children
        
        i, j = 0, 0
        content = 0
        g.sort() 
        s.sort() 
        
        while i < len(g) and j < len(s) :
            if s[j] >= g[i] : 
                content += 1
                i += 1
            j += 1
        return content

4. Conclusion