0455. Assign Cookies.js

// 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 gi, which is the minimum size of a cookie that the child will be content with; and each cookie j has a size sj.If sj >= gi, 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.

// Note:
// You may assume the greed factor is always positive.
// You cannot assign more than one cookie to one child.

// Example 1:

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


// 1) 贪心
/**
 * @param {number[]} g
 * @param {number[]} s
 * @return {number}
 */
const findContentChildren = (g, s) => {
  let j = 0
  let res = 0
  g = g.sort((a, b) => a - b)
  s = s.sort((a, b) => a - b)
  for (let i = 0; i < g.length; i++) {
    while (j < s.length) {
      if (s[j] >= g[i]) {
        res++
        j++
        break
      }
      j++
    }
  }
  return res
}
// Runtime: 92 ms, faster than 55.18 % of JavaScript online submissions for Assign Cookies.
// Memory Usage: 37.6 MB, less than 100.00 % of JavaScript online submissions for Assign Cookies.


// 2) 贪心
const findContentChildren = (g, s) => {
  let i = 0
  g = g.sort((a, b) => a - b)
  s = s.sort((a, b) => a - b)
  for (let j = 0; j < s.length && i < g.length; j++) {
    if (s[j] >= g[i]) {
      i++
    }
  }
  return i
}
// Runtime: 96 ms, faster than 39.76 % of JavaScript online submissions for Assign Cookies.
// Memory Usage: 37.7 MB, less than 100.00 % of JavaScript online submissions for Assign Cookies.


// 3) 贪心
const findContentChildren = (g, s) => {
  g = g.sort((a, b) => a - b)
  s = s.sort((a, b) => a - b)
  let i = 0
  let j = 0
  let count = 0
  while (i < s.length) {
    if (s[i] >= g[j]) {
      count++
      j++
    }
    i++
  }
  return count
}
// Runtime: 60 ms, faster than 100.00 % of JavaScript online submissions for Assign Cookies.
// Memory Usage: 37.5 MB, less than 100.00 % of JavaScript online submissions for Assign Cookies.