Python O(nlogn) greedy solution with explaination


  • 0

    The best way to satisfy children is to avoid waste, start from the child with lowest si, we need to find a smallest cookie that satisfy him/her, if we cant find one, then we can not satisfy the rest children.

    class Solution(object):
        def findContentChildren(self, g, s):
            """
            :type g: List[int]
            :type s: List[int]
            :rtype: int
            """
            
            s.sort()
            count, i = 0, 0
            
            for child in sorted(g):
                # find the best cookie to satisfy this child
                while i < len(s) and s[i] < child:
                    i += 1
                if i != len(s):  # satisfy a child
                    count += 1
                    i += 1
                else:   # cant find any cookie to satisfy a child
                    break
            return count
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.