Assume you are an awesome parent of N children and want to give your children some cookies out of given M cookies. But, you should give each child atmost one cookie.
Each child i has a greed factor greed [ i ], which is the minimum size of cookie that the child will be content with; and each cookie j has a size sz [ j ]. If sz [ j ] >= greed [ i ], we can assign the cookie j to the child i^{th}, and the child i will be content.
Your goal is to maximize the number of your content children and return the maximum number.
Example 1:
Input:
N = 3 
M = 2
greed [ ] = {1, 2, 3}
sz [ ] = {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 return 1.
 
Example 2:
Input:
N = 2 
M = 3
greed [ ] = {1, 2}
sz [ ] = {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.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function maxChildren() which takes the interger N, integer M and two integer array greed [ ] and sz [ ] as parameters and returns the maximum number of content children.
Expected Time Complexity: O(max( NlogN , MlogM ))
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤  5 * 10^{4}
1 ≤ M ≤  5 * 10^{4}
1 ≤ greed [ i ] , sz [ i ] ≤ 10^{9}

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Data structures

Starter code: #User function Template for python3



class Solution:

    def maxChildren(self, N, M, greed, sz):

        # Code here

Solutions:
class Solution:

	def maxChildren(self, N, M, greed, sz):
		greed.sort()
		sz.sort()
		(i, j) = (0, 0)
		child = 0
		while i < N and j < M:
			if greed[i] <= sz[j]:
				child += 1
				i += 1
				j += 1
			elif greed[i] > sz[j]:
				j += 1
		return child


class Solution:

	def maxChildren(self, N, M, greed, sz):
		greed.sort()
		sz.sort()
		i = N - 1
		j = M - 1
		count = 0
		while i >= 0 and j >= 0:
			if greed[i] <= sz[j]:
				count += 1
				i -= 1
				j -= 1
			else:
				i -= 1
		return count


class Solution:

	def maxChildren(self, N, M, greed, sz):
		greed.sort()
		sz.sort()
		count = 0
		j = 0
		for i in range(N):
			while j < M and greed[i] > sz[j]:
				j = j + 1
			if j == M:
				break
			else:
				count = count + 1
				j = j + 1
		return count


class Solution:

	def maxChildren(self, N, M, greed, sz):
		greed.sort()
		sz.sort()
		i = 0
		j = 0
		maxContentChild = 0
		while i < N and j < M:
			greedFactor = greed[i]
			size = sz[j]
			if greedFactor <= size:
				i += 1
				j += 1
				maxContentChild += 1
			else:
				j += 1
		return maxContentChild


class Solution:

	def maxChildren(self, N, M, greed, sz):
		count = 0
		greed.sort()
		sz.sort()
		(cookie_i, kid_i) = (0, 0)
		while cookie_i < len(sz) and kid_i < len(greed):
			if sz[cookie_i] >= greed[kid_i]:
				kid_i += 1
				count += 1
			cookie_i += 1
		return count


class Solution:

	def maxChildren(self, N, M, greed, sz):
		greed.sort(reverse=True)
		sz.sort(reverse=True)
		curr = 0
		total = 0
		for i in range(len(greed)):
			if curr < len(sz) and sz[curr] >= greed[i]:
				total += 1
				curr += 1
		return total


class Solution:

	def maxChildren(self, N, M, greed, sz):
		greed.sort()
		sz.sort()
		ans = 0
		i = 0
		for j in range(M):
			if i == N:
				break
			elif sz[j] >= greed[i]:
				ans += 1
				i += 1
		return ans


class Solution:

	def maxChildren(self, N, M, greed, sz):
		greed.sort()
		sz.sort()
		child = len(greed) - 1
		cookie = len(sz) - 1
		ans = 0
		while cookie >= 0 and child >= 0:
			if greed[child] <= sz[cookie]:
				ans += 1
				child = child - 1
				cookie = cookie - 1
			else:
				child = child - 1
		return ans


class Solution:

	def maxChildren(self, N, M, greed, sz):
		greed.sort(reverse=True)
		sz.sort(reverse=True)
		c = 0
		t = 0
		for i in range(N):
			if c < M and sz[c] >= greed[i]:
				c += 1
				t += 1
		return t


class Solution:

	def maxChildren(self, N, M, greed, sz):
		greed.sort(reverse=True)
		sz.sort(reverse=True)
		g = 0
		s = 0
		count = 0
		while s < M and g < N:
			if greed[g] <= sz[s]:
				count += 1
				s += 1
				g += 1
			else:
				g += 1
		return count


class Solution:

	def maxChildren(self, N, M, greed, sz):
		greed.sort()
		sz.sort()
		i = 0
		for item in sz:
			if item >= greed[i]:
				i += 1
			if i == N:
				return N
		return i


class Solution:

	def maxChildren(self, N, M, greed, sz):
		greed.sort()
		sz.sort()
		count = 0
		i = 0
		for item in greed:
			while i < M and sz[i] < item:
				i += 1
			if i == M:
				break
			count += 1
			i += 1
		return count


class Solution:

	def maxChildren(self, N, M, greed, sz):
		greed.sort(reverse=True)
		sz.sort(reverse=True)
		j = 0
		ans = 0
		for i in greed:
			if j < M and sz[j] >= i:
				ans += 1
				j += 1
		return ans


class Solution:

	def maxChildren(self, N, M, g, c):
		g.sort(reverse=True)
		c.sort(reverse=True)
		curr = 0
		total = 0
		for i in range(len(g)):
			if curr < len(c) and c[curr] >= g[i]:
				total += 1
				curr += 1
		return total


class Solution:

	def maxChildren(self, N, M, greed, sz):
		greed.sort(reverse=True)
		sz.sort(reverse=True)
		i = 0
		j = 0
		satisfied = 0
		while i < len(greed) and j < len(sz):
			if greed[i] <= sz[j]:
				satisfied += 1
				i += 1
				j += 1
			else:
				i += 1
		return satisfied


class Solution:

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


class Solution:

	def maxChildren(self, N, M, greed, sz):
		i = 0
		j = 0
		g = sorted(greed)
		s = sorted(sz)
		while i < N and j < M:
			if g[i] <= s[j]:
				i += 1
			j = j + 1
		return i


class Solution:

	def maxChildren(self, N, M, greed, sz):
		greed.sort()
		sz.sort()
		childi = 0
		cookiei = 0
		while cookiei < M and childi < N:
			if sz[cookiei] >= greed[childi]:
				childi += 1
			cookiei += 1
		return childi


class Solution:

	def maxChildren(self, N, M, greed, sz):
		greed.sort()
		sz.sort()
		count = 0
		i = 0
		for j in sz:
			if i < len(greed) and j >= greed[i]:
				count += 1
				i += 1
		return count


class Solution:

	def maxChildren(self, N, M, greed, sz):
		greed.sort()
		sz.sort()
		(it, ig) = (0, 0)
		while it < M and ig < N:
			if sz[it] >= greed[ig]:
				ig += 1
			it += 1
		return ig


class Solution:

	def maxChildren(self, n, m, greed, sz):
		greed.sort()
		sz.sort()
		greed = greed[::-1]
		sz = sz[::-1]
		curr = 0
		total = 0
		for i in range(0, n):
			if curr < m and greed[i] <= sz[curr]:
				curr = curr + 1
				total = total + 1
		return total


class Solution:

	def maxChildren(self, N, M, greed, sz):
		greed.sort()
		sz.sort()
		(gp, sp) = (0, 0)
		count = 0
		while gp < N and sp < M:
			if sz[sp] >= greed[gp]:
				count += 1
				sp += 1
				gp += 1
			else:
				sp += 1
		return count


class Solution:

	def maxChildren(self, N, M, greed, sz):
		greed.sort()
		sz.sort()
		i = j = ans = 0
		while i < len(greed) and j < len(sz):
			if sz[j] >= greed[i]:
				i += 1
				ans += 1
			j += 1
		return ans