NeetCode 150 [Binary Search]:medium 2/5

NeetCodeのSolutionを書いていく

Koko Eating Bananas

問題概要

整数の配列pilesが与えられます。
piles[i]はi番目の山のバナナの数です。
整数hも与えられ、hは全てのバナナを食べきらないといけない時間です。

バナナを食べる時速kを決めます。
毎時間山を決めて、k個のバナナをその山から食べます。
山のバナナがk個以下であれば食べ切れますが、食べ終わっても移動はできません。

h時間以内にバナナを食べきる最小のkを返しなさい。

例

Input: piles = [1,4,3,2], h = 9
Output: 2

Input: piles = [25,10,23,4], h = 4
Output: 25

制約

• pilesのサイズは1以上1000以下
• hはpiles.length以上1,000,000以下
• piles[i]は1以上1,000,000,000以下

計算：O(nlogm) nは配列数。mは配列の最大値。
メモリ：O(1)

ヒント1

• hは常にpiles.lengthより大きいです
• 回答(k)の上限はわかりますか？
• xのバナナの山を食べるにはどれくらい時間がかかりますか？

kの上限は、pilesの山の最大値？piles = [1,4,3,2]だったら4？
xのバナナの山を食べるには -(-x/k)の時間がかかる。（切り上げ除算）

ヒント2

• h時間以内にバナナを食べ終わらなくてはなりません。
• kの上限値はわかりますか？

ヒント1との違いがわからん。。。

ヒント3

• kの上限値はpilesの最大値です。Kokoが最大の山を1時間で食べられるならその他の山も1時間で食べられるからです

ヒント1の時点でその様に思っていたけども、だいぶ手厚いヒントだったんですね。

ヒント4

• pilesの最大値をm、pilesの長さをnとすると、強引にやると1~mの数字でkと時間を確認すればできますがO(n*m)の時間がかかります。
• 効率的にできますか？検索アルゴリズムが役に立つはずです。

そうか！1~mの数字をバイナリサーチ的に使えばよいのか！
つまり、k=m/2から調査を開始してh以下に収まっていればk=m/2/2を評価対象にする、そうでなければk=m*3/4を評価対象にする。
評価を繰り返してkの最小値を返せばOK！

from typing import List


class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        def ceil(x, y):
            return -(-x // y)

        def get_time(k):
            v = 0
            for pile in piles:
                v += ceil(pile, k)
            return v

        # 戻り値kの上限値はpipesの最大値
        m = max(piles)

        # 1~mの中で最小のkを探す
        result = m
        min_k = 1
        max_k = m
        while True:
            k = (min_k + max_k) // 2
            if get_time(k) <= h:
                if result > k:
                    result = k
                if max_k == k:
                    break
                max_k = k
            else:
                if min_k == k:
                    break
                min_k = k

        return result