455.分发饼干

原题地址

贪心算法的入门级题目

本题思路很简单，那就是给一个孩子的饼干应该尽量小并且又能满足该孩子

这也就是贪心算法。局部得到最优解从而使全局最优。

那么重点来了，我们怎么证明在这道题中，局部最优能够推出全局最优呢？换种说法，我们怎么知道贪心策略适用于这道题目？

反证法：

• 假设饼干从小到大排列。在某次选择中，贪心算法选择给当前满足度最小的孩子分配第m块饼干，所以第m块饼干是满足该孩子的最小饼干，是当前最优的。
• 现在我们来反证。假设存在一种最优策略比贪心策略更好，给孩子分配的是第n块饼干，n > m，那么这次分配完毕后，显然使用贪心策略剩下的饼干要比最优策略更大，因此在后续的分配中，贪心策略更能满足更多的孩子，所以最优策略不如贪心策略，矛盾。
• 因此，贪心策略是最优策略。

算法思路

先将两数组从小到大排序，采用双指针进行遍历。

python代码

def findContentChildren(self, g: List[int], s: List[int]) -> int:
    g.sort()
    s.sort()
    p = q = 0
    while p < len(g) and q < len(s):
        if s[q] >= g[p]:
            p += 1
        q += 1
    return p