用贪心算法来分饼干

贪心算法简介

顾名思义，贪心算法采取“贪心”策略，即：保证每次局部都为最优解，从而使最后得到的结果为全局最优解。

题目描述

假设你是一位很棒的家长, 想要给你的孩子们一些小饼干. 但是每个孩子最多只能给一块饼干. 对每个孩子i，都有一个胃口值g[i], 这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干j, 都有一个尺寸s[j]. 如果s[j] >= g[i], 我们可以将这个饼干j分配给孩子i, 这个孩子会得到满足. 你的目标是尽可能满足越多数量的孩子, 并输出这个最大数值.

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/assign-cookies

示例

输入: g = [1,2], s = [1,2,3]

输出: 2

解释: 可以给两个孩子吃[1,2], [1,3], [2, 3] 这三种组合的的任意一种，每个孩子都能吃饱，则输出为 2。

题目详解

根据贪心算法，优先喂饥饿度最小的孩子，且尽量使剩下的饼干满足饥饿度更大的孩子。贪心策略即为：给剩余小孩中饥饿度最小的孩子能饱腹的最少饼干。

因此符合贪心策略的便捷实践为：分别按照从小到大的顺序给饥饿度与饼干尺寸排序，这样便可以从饥饿度最小的孩子和尺寸最下的饼干开始计算。

算法实现

var findContentChildren = (g, s) => {
  if (!g || !s){
    return 0
  }
  g = g.sort((a,b) => a - b)
  s = s.sort((a,b) => a - b)
  let child = 0
  let cookie = 0
  const childrenLen = g.length
  const cookiesLen = s.length
  while(child < childrenLen &&
    cookie < cookiesLen) {
    if (g[child] <= s[cookie]) {
      ++child
    }
    ++cookie
  }
  return child
}