Fair Distribution Of Cookies - Leetcode Solution

Problem:

You have n cookies to distribute among k children. Each child i has a greed factor gi, which represents the minimum size of a cookie that the child will be content with. Each cookie j has a size sj. If the size of cookie j is greater than or equal to the greed factor of child i, then child i will be content with the cookie.

Your goal is to maximize the number of content children and output this maximum number.

Input: The input consists of two arrays, one representing the greed factors of the children and the other representing the sizes of the cookies.

Output: The output consists of a single integer, which represents the maximum number of content children.

Constraints: 1 <= n, k <= 210^4 1 <= gi, sj <= 210^9

Solution:

This problem can be solved using a greedy approach. We can start by sorting both the greed factor and the cookie sizes in non-decreasing order. Once we have sorted the arrays, we can start from the first child and the first cookie and check if the size of the cookie is greater than or equal to the greed factor of the child. If it is, we can give the cookie to the child and move to the next child and the next cookie. If it is not, we can move to the next cookie and check again. If we have exhausted all the cookies and we still cannot find a cookie for the current child, we move to the next child.

We can keep track of the number of content children by maintaining a count for each cookie that is given to a child. When we give a cookie to a child, we increment the count for that cookie. Once we have processed all the children, we add up the counts for all cookies and return the total count.

Code:

The code for the solution is as follows:

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()
        i, j, res = 0, 0, 0
        while i < len(g) and j < len(s):
            if s[j] >= g[i]:
                res += 1
                i += 1
                j += 1
            else:
                j += 1
        return res

Time Complexity:

The time complexity of the solution is O(n*log(n)) as we are sorting the arrays and then processing each element once.

1