Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor gi, which is the minimum size of a cookie that the child will be content with; and each cookie j has a size sj. If sj >= gi, we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.


Note:
You may assume the greed factor is always positive. 
You cannot assign more than one cookie to one child.


Example 1:

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



Example 2:

Input: [1,2], [1,2,3]

Output: 2

Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2. 
You have 3 cookies and their sizes are big enough to gratify all of the children, 
You need to output 2.

Source: leetcode | Difficulty: EASY
Tags: Data structures

Sorting

Amortized analysis

Greedy algorithms

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

Solutions:
class Solution:

	def findContentChildren(self, g, s):
		res = 0
		heapq.heapify(g)
		s.sort()
		for num in s:
			if not g:
				break
			elif g[0] <= num:
				res += 1
				heapq.heappop(g)
		return res


class Solution:

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


class Solution:

	def findContentChildren(self, g, s):
		g.sort()
		s.sort()
		(i, j) = (0, 0)
		happyKids = 0
		while i < len(g) and j < len(s):
			if s[j] >= g[i]:
				happyKids += 1
				i += 1
			j += 1
		return happyKids


class Solution:

	def findContentChildren(self, g, s):
		(g.sort(), s.sort())
		count = 0
		i = 0
		while count < len(g) and i < len(s):
			if s[i] >= g[count]:
				count += 1
			i += 1
		return count


class Solution:

	def findContentChildren(self, g, s):
		g = sorted(g)
		s = sorted(s)
		result = 0
		i = 0
		j = 0
		while i < len(g) and j < len(s):
			if g[i] <= s[j]:
				result = result + 1
				i = i + 1
				j = j + 1
			else:
				j = j + 1
		return result


class Solution:

	def findContentChildren(self, g, s):
		s.sort()
		g.sort()
		total = 1
		child_to_give = []
		child_index = 0
		start_i = 0
		for j in range(0, len(g)):
			for i in range(start_i, len(s)):
				if s[i] >= g[j]:
					child_to_give.append(j)
					start_i = i + 1
					break
		print(child_to_give)
		return len(child_to_give)


class Solution:

	def findContentChildren(self, g, s):
		g.sort()
		s.sort()
		print(g)
		print(s)
		count_child = 0
		count_cookie = 0
		while count_child < len(g) and count_cookie < len(s):
			if g[count_child] <= s[count_cookie]:
				count_child += 1
			count_cookie += 1
		return count_child


class Solution:

	def findContentChildren(self, g, s):
		g.sort()
		s.sort()
		(index, result) = (0, 0)
		while index < len(s) and len(g) > 0:
			if s[index] >= g[0]:
				result += 1
				index += 1
				g.remove(g[0])
			else:
				index += 1
		return result