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
            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
            return count

Log in to reply

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