九章演算法 | Google 面試題：分餅乾

01-28

撰文 | JZ

專欄 | 九章演算法

題目描述

假設你有一群孩子和一些餅乾，每一塊餅乾j大小為s(j)，同時每一個孩子i，被分到的餅乾大小至少為g(i)，即s(j)>=g(i)時，這個孩子才會滿足，g(i)成為孩子i的滿足度。你的目標是將餅乾分配給孩子，使得到滿足的孩子儘可能多。保證每個g(i)為正且不能將多塊餅乾分給一個孩子或將一塊餅乾分給多個孩子。

輸出樣例

樣例1:

輸入: [1,2,3], [1,1]

輸出: 1

說明: 三個孩子的滿足度分別為1,2,3，兩塊餅乾的大小均為1。餅乾的大小為1，只能滿足第一個孩子，所以輸出1。

樣例2:

輸入: [1,2], [1,2,3]

輸出: 2

說明: 兩個孩子的滿足度分別為1,2，三塊餅乾的大小分別為1,2,3。這三塊餅乾的大小足以滿足這兩個孩子，所以輸出2。

解題思路分析

1. 分析

直覺上，要使滿足的孩子儘可能多，分配給每個孩子的餅乾應該儘可能小。如果把大的餅乾分配給滿足度較小的孩子，顯然會造成浪費。這樣，我們可以按g(i)從小到大給孩子分配餅乾，同時，為了不浪費餅乾，對於要分配給某個孩子的餅乾，也從剩下的餅乾中找到最小的能滿足這個孩子的餅乾。按g(i)從小到大分配餅乾的好處是，當把s(j)分配給g(i)之後，對於下一個孩子g(i+1)，我們就不用考慮s(j)之前的餅乾了，只需考慮s(j)之後的餅乾（這裡假設g(i),s(i)為從小到大排列）。因為，如果s(j)之前還有可以滿足g(i+1)的餅乾，那這塊餅乾也必然可以滿足g(i)，那s(j)就不是剩餘餅乾中可以滿足g(i)的最小的餅乾了。

2. 實現

將g與s都從小到大排列，再用兩根指針i,j，如果g(i)<=s(j)，則將s(j)分配給g(i)，再看下一個孩子與下一塊餅乾，i與j均自增；否則，應依次增大j去尋找能滿足g(i)的s(j)。這種方法叫做two pointer。設孩子數與餅乾數的較大值為n，則排序的時間複雜度為O(n*log(n))，兩根指針的時間的複雜度為O(n)，總的時間複雜度為O(n*log(n))。

3. 證明

那麼這樣的貪心演算法是正確的嗎？是的。下面給出簡單的分析。首先仍然假設g(i)已從小到大排序，所以g(0)為最小值。對於一個最優的方案（即能滿足最多孩子的方案），假設這個方案里能滿足的孩子中滿足度最小的是g(i)，而將s(j)分配給了g(i)，那麼有s(j)>=g(i)>=g(0)，故我們可以把g(i)換成g(0)而得到另一個最優方案。把g(0)與s(j)從原問題中去掉，則得到了一個比原問題規模略小但形式相同的新問題。對於新問題的分析與原問題相同。這樣，我們就可以把原最優方案中的孩子依次替換成g(0)，g(1)，……，g(ans-1)，ans為最優方案滿足的孩子個數。因此，我們總可以去先滿足滿足度最小的孩子來獲得最優方案。

4. 實現

只要每次給出的餅乾是能滿足當前的孩子的最小的餅乾，以什麼樣的順序給孩子分配餅乾其實是無所謂的（如果不存在能滿足當前孩子的餅乾，則跳過這個孩子），最終的答案都是一樣的。具體分析比較繁瑣，這裡不再給出，感興趣的讀者可以試著從以下角度分析：對於一種孩子分配順序，如果交換某對相鄰兩個孩子的順序，會對最終結果造成怎樣的影響。

5. Follow up

如果可以把多塊餅乾分給一個孩子，怎麼做？

參考程序

面試官角度分析

此題的最優演算法是貪心演算法。如果能想到貪心演算法並給出演算法框架，就可以達到hire的程度。對於貪心演算法的學習，可以參考的意見如下 link:

還在浪費時間學貪心演算法么？告訴你三個不需要學習貪心法的理由！

LintCode相關問題

Majority Number

Create Maximum Number

Jump Game II

Jump Game

Gas Station

Delete Digits

Linked List Cycle II

Linked List Cycle

九章官網參考代碼鏈接：

Majority Number題解

Create Maximum Number題解

Jump Game II題解

Jump Game題解

Gas Station題解

Delete Digits題解

Linked List Cycle II題解

Linked List Cycle題解