Algorithms and Data Structures

Sample Problem

You are given two integer arrays:

• greeds, where greeds[i] represents the minimum size of a cookie that a child needs to to be satisfied.
• cookies, where cookies[j] represents the size of a cookie.

Assign cookies such that as many children as possible are satisfied. Each child can receive at most one cookie, and each cookie can be given to only one child.

A Greedy Algorithm

def num_satisfied_children(greeds: List[int], cookies: List[int]) -> int:
  greeds.sort()
  cookies.sort()

  count = 0
  g_idx, c_idx = 0, 0
  while g_idx < len(greeds) and c_idx < len(cookies):
    if cookies[c_idx] >= greeds[g_idx]:
      count += 1
      g_idx += 1

    c_idx += 1

  return count