Assign Cookies

🏠 ⬅️ ➡️

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 g[i], which is the minimum size of a cookie that the child will be content with; and each cookie j has a size s[j]. If s[j] >= g[i], 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.

Example 1:

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

Constraints:

  • 1 <= g.length <= 3 * 104
  • 0 <= s.length <= 3 * 104
  • 1 <= g[i], s[j] <= 231 - 1
Note: This problem is from LeetCode.
✅ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer :: n_children, n_cookies
    integer, dimension(:), allocatable :: greed_factors
    integer, dimension(:), allocatable :: cookie_sizes
    integer :: i, j
    integer :: max_content_children

    ! read input
    read(*,*) n_children
    allocate(greed_factors(n_children))
    do i = 1, n_children
        read(*,*) greed_factors(i)
    end do
    read(*,*) n_cookies
    allocate(cookie_sizes(n_cookies))
    do i = 1, n_cookies
        read(*,*) cookie_sizes(i)
    end do

    ! solve problem
    max_content_children = 0
    do i = 1, n_children
        do j = 1, n_cookies
            if (cookie_sizes(j) >= greed_factors(i)) then
                max_content_children = max(max_content_children, 1)
                exit
            end if
        end do
    end do

    ! print output
    write (*,*) max_content_children

end program main
❌ Compiled
❌ Executed
❌ Correct 
module MaxContentChildren
  implicit none
contains
  subroutine solve(g, s, n, m, result)
    integer, intent(in) :: n, m
    integer, intent(in) :: g(n), s(m)
    integer, intent(out) :: result

    integer :: i, j, k
    integer :: max_content

    ! Initialize variables
    max_content = 0
    k = 1

    ! Loop through the children
    do i = 1, n
      ! Loop through the cookies
      do j = k, m
        ! If the cookie size is greater than or equal to the child's greed factor,
        ! assign the cookie to the child and increment the number of content children
        if (s(j) >= g(i)) then
          max_content = max_content + 1
          k = j + 1
          exit
        end if
      end do
    end do

    ! Output the maximum number of content children
    result = max_content
  end subroutine solve
end module MaxContentChildren

program test
  use MaxContentChildren
  implicit none

  integer, parameter :: n = 3
  integer, parameter :: m = 2
  integer :: g(n) = [1, 2, 3]
  integer :: s(m) = [1, 1]
  integer :: result

  call solve(g, s, n, m, result)
  write (*,*) result

  g = [1, 2]
  s = [1, 2, 3]
  call solve(g, s, n, m, result)
  write (*,*) result
end program test
🌐 Data from online sources 
def find_content_children(g, s):
    g.sort()
    s.sort()
    i = j = 0

    while i < len(g) and j < len(s):
        if s[j] >= g[i]:
            i += 1

        j += 1

    return i

The algorithm first sorts both the greed factors of children `g` and the sizes of cookies `s`. Next, two pointers are declared, `i` for the greed factors and `j` for the cookies.

The algorithm then iterates through the sorted lists in parallel using a while loop until either the greed factors or the cookies run out. Inside the loop, we check if the current cookie s[j] is greater than or equal to the current greed factor g[i]. If it is, that means the child is content and we increment the i pointer to the next child. In both cases (whether the child is content or not), we move on to the next cookie by incrementing the j pointer. The algorithm returns the number of content children (i) once the loop is done.

🌐 Data from online sources 
#include <vector>
#include <algorithm>

int findContentChildren(std::vector<int>& g, std::vector<int>& s) {
    std::sort(g.begin(), g.end());
    std::sort(s.begin(), s.end());
    int i = 0, j = 0;

    while (i < g.size() && j < s.size()) {
      if (s[j] >= g[i]) {
        i++;
      }

      j++;
    }

    return i;
}

The algorithm first sorts both the greed factors of children `g` and the sizes of cookies `s`. Next, two pointers are declared, `i` for the greed factors and `j` for the cookies.

The algorithm then iterates through the sorted lists in parallel using a while loop until either the greed factors or the cookies run out. Inside the loop, we check if the current cookie s[j] is greater than or equal to the current greed factor g[i]. If it is, that means the child is content and we increment the i pointer to the next child. In both cases (whether the child is content or not), we move on to the next cookie by incrementing the j pointer. The algorithm returns the number of content children (i) once the loop is done.