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