455. Assign Cookies

Easy

Problem:

Each child must be given one cookie. Each child, denoted as child_i, has a greed factor, which represents the minimum size of the cookie the child will be satisfied with. Each cookie, cookie_j, has a size, and a child will be satisfied and accept the cookie if s[cookie_j] >= g[child_i]. Print the maximum number of children who can be given a cookie.

Input: g = [1,2,3], s = [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.

https://leetcode.com/problems/assign-cookies/description/

What to learn:

bisect_left() returns the index of the found value's position, while bisect_right() returns the index after the found value's position.

>>> bisect.bisect_left([1,2,3,4,5], 3)
2
>>> bisect.bisect_right([1,2,3,4,5], 3)
3

Solution:

Greedy algorithm

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()

        g_p, s_p = 0, 0
        while g_p < len(g) and s_p < len(s):
            if s[s_p] >= g[g_p]:
                g_p += 1
            s_p += 1
            
        return g_p

Binary search

While iterating through one list, search for the corresponding index in the other list using binary search. If the found index is greater than the current number of children assigned cookies, it means that more cookies can be given, so increase the count of children who can be given cookies by one.

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()

        result = 0
        for i in s:
            index = bisect.bisect_right(g, i)
            if index > result:
                result += 1
        return result

Applying to the example:

• First Iteration (i = 1):

  • bisect.bisect_right(g, 1) will return 1 since 1 can be inserted at index 1 in g (after the first element, which is also 1).

  • index = 1, which is greater than the current result (0), so one child can be satisfied with this cookie.

  • result is incremented to 1.

• Second Iteration (i = 1 again):

  • bisect.bisect_right(g, 1) will again return 1. But this time, index = 1 is not greater than the current result (which is now 1).

  • This means the second cookie cannot satisfy a new child. So, result remains 1.

Thus, the output is 1, indicating that only one child can be satisfied with the given cookies.