[LeetCode] (455) Assign Cookies

Basic idea: using a greedy algorithm, prioritize satisfying kids with lower greed and assign cookies this way as many as possible.

Implementation Apple:

class Solution(object):
    def findContentChildren(self, g, s):
        """
        :type g: List[int]
        :type s: List[int]
        :rtype: int
        """
        g.sort()
        s.sort()
        count = 0
        start = 0
        for greed in g:
            for i, size in enumerate(s[start:]):
                if size >= greed:
                    count += 1
                    start += i + 1
                    break
        return count

Time Complexity is O(n).

 

Implementation Banana:

class Solution(object):
    def findContentChildren(self, g, s):
        """
        :type g: List[int]
        :type s: List[int]
        :rtype: int
        """
        g.sort()
        s.sort()
        count = 0
        for size in s:
            if count < len(g) and size >= g[count]:
                count += 1
        return count

Time Complexity is also O(n).

Related posts