Pythonでk日以内にすべてのスカイダイビング申込を処理するための最小飛行機定員を求めるプログラム

数値のリスト nums があるとします。各要素は、一緒にスカイダイビングをしたいグループの人数を表しています。また、もうひとつの値 k は、スカイダイビングの申し込みが可能な日数を表します。ここで、すべてのリクエストを k 日以内に処理できるようにするために必要な、飛行機の最小定員を求めます。

ただし、リクエストは与えられた順番どおりに処理しなければならず、飛行機は1日に1回しか飛べないものとします。

たとえば、入力が nums = [16, 12, 18, 11, 13]、k = 3 の場合、出力は 28 になります。これは、28人乗りの飛行機を使えば、グループを [16, 12]、[18]、[11, 13] のように3日間に分けて処理できるからです。

解き方のアプローチ

この問題は二分探索（バイナリサーチ）を使うことで効率的に解けます。答えとなる最小定員の候補範囲は、「リスト内の最大値（それ未満だとどのグループも乗せられない）」から「全要素の合計値（1日で全部乗せる場合）」までです。この範囲に対して二分探索を行い、各候補値について k 日以内に収まるかどうかをシミュレーションで判定します。

具体的には、次の手順で進めます。

• nums が空なら 0 を返す
• 探索範囲の下限 start を nums の最大値、上限 end を全要素の合計値に設定する
• start < end の間、以下を繰り返す
  • mid := (start + end) / 2 を候補の定員とする
  • days := 1、temp := 0 として初期化する
  • nums の各要素 num について、temp + num > mid なら日数を1増やして temp := num とし、そうでなければ temp := temp + num とする
  • 必要日数 days が k より大きければ start := mid + 1、そうでなければ end := mid とする
• 最後に start を返す

実装例

以下は、上記のアルゴリズムを実装したPythonコードです。

class Solution:
    def solve(self, nums, k):
        if not nums:
            return 0

        start, end = max(nums), sum(nums)

        while start < end:
            mid = (start + end) // 2

            days = 1
            temp = 0
            for num in nums:
                if temp + num > mid:
                    days += 1
                    temp = num
                else:
                    temp += num

            if days > k:
                start = mid + 1
            else:
                end = mid

        return start

ob = Solution()
nums = [16, 12, 18, 11, 13]
k = 3
print(ob.solve(nums, k))

入力

[16, 12, 18, 11, 13], 3

出力

28

計算量について

このアルゴリズムの時間計算量は O(n × log S) です。ここで n はグループ数、S は全人数の合計です。二分探索の各ステップで配列を一度走査するため、貪欲法だけで全範囲を試す方法よりもはるかに効率的に最小定員を求められます。