LeetCode Entry

455. Assign Cookies

1.01.2024 easy 2024 kotlin

Max count of greedy children g[Int] to assign cookies with sizes s[Int].

455. Assign Cookies easy blog post substack youtube image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/458

Problem TLDR

Max count of greedy children g[Int] to assign cookies with sizes s[Int].

Intuition

The optimal way to assign cookies is to start with less greed. We can put cookies and children in two PriorityQueues or just sort two arrays and maintain two pointers.

Approach

  • PriorityQueue is a more error-safe solution, also didn’t modify the input.
  • Careful with the pointers, check yourself with simple examples: g=[1] s=[1], g=[2] s=[1]

Complexity

  • Time complexity: \(O(nlog(n))\)

  • Space complexity: \(O(1)\)

Code


  fun findContentChildren(g: IntArray, s: IntArray): Int {
    g.sort()
    s.sort()
    var j = 0
    return g.count {
      while (j < s.size && s[j] < it ) j++
      j++ < s.size
    }
  }