#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/greedy-algorithms/greedy-optimization/assign-cookies-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/greedy-algorithms/greedy-optimization/assign-cookies-implementation

Repovive

Assign Cookies - Implementation - Greedy Optimization | Greedy Algorithms | Repovive

Repovive.

Greedy Algorithms8 sections · 317 units14h total

Open in Course

Assign Cookies - Implementation

The code

Here is the solution:

function findContentChildren(greed, cookies)
 sort greed ascending
 sort cookies ascending
 child := 0
 cookie := 0
 while child < length(greed) and cookie < length(cookies)
 if cookies[cookie] >= greed[child] then
 child := child + 1
 cookie := cookie + 1
 return child

Time: $O(n \log n + m \log m)$ for sorting. Space: $O(1)$ extra.

The two-pointer approach: try to satisfy children in order. If current cookie works, move to next child. Either way, move to next cookie.