Pythonで指定された制約条件下ですべてのジョブを完了する最小時間を求める方法

それぞれ所要時間の異なるジョブの配列があり、これらのジョブを担当する作業者が k 人いるとします。さらに、各作業者がジョブ 1 単位を処理するのにかかる時間 t も与えられています。このとき、次の制約条件下で、すべてのジョブを完了させるために必要な最小時間を求めます。

• 各作業者に割り当てられるのは連続したジョブのみであること。
• 複数の作業者が 1 つのジョブを分担して処理することはできないこと。

たとえば、入力が k = 4、t = 5、job = {12, 6, 9, 15, 5, 9} の場合、出力は 75 になります。これは [12]、[6, 9]、[15]、[5, 9] のようにジョブを 4 人に分割して割り当てることで達成できます。

解法の考え方：二分探索

この問題では、「ある時間 X を上限としたとき、k 人以下の作業者で全ジョブを処理できるか？」という判定が可能です。X を大きくするほど true になりやすく、小さくするほど false になりやすい（単調性がある）ため、二分探索によって最小の X を効率的に絞り込めます。

ステップ 1：判定関数 is_valid() を定義する

is_valid() は、仮の上限時間 time、作業者数 K、ジョブ配列 job を受け取ります。

• n := ジョブの個数
• count := 1（使用した作業者数）、curr_time := 0（現在の作業者の累積時間）、i := 0 で初期化
• i < n の間、以下を繰り返す：
  • curr_time + job[i] > time の場合 → curr_time := 0、count := count + 1（次の作業者に切り替え）
  • それ以外の場合 → curr_time := curr_time + job[i]、i := i + 1
• 最後に、count <= K であれば true を返す

ステップ 2：メイン処理で二分探索を行う

• n := ジョブの個数、end := 全ジョブの合計時間、begin := 0
• res := end（暫定解）、job_max := ジョブの中で最大の所要時間
• begin <= end の間、以下を繰り返す：
  • mid := (begin + end) / 2 の整数部分
  • mid >= job_max かつ is_valid(mid, K, job) が true の場合 → res := min(res, mid)、end := mid - 1
  • それ以外の場合 → begin := mid + 1
• 最後に res * T を返す（1 単位あたりの時間を掛けて実際の所要時間に変換）

ここで「mid >= job_max」という条件が重要です。上限時間が最大のジョブの所要時間より短いと、そのジョブをどの作業者も完了できないためです。

Python 実装例

def is_valid(time, K, job):
    n = len(job)
    count = 1
    curr_time = 0
    i = 0
    while i < n:
        if curr_time + job[i] > time:
            curr_time = 0
            count += 1
        else:
            curr_time += job[i]
            i += 1
    return count <= K


def get_minimum_time(K, T, job):
    n = len(job)
    end = 0
    begin = 0
    for i in range(n):
        end += job[i]
    res = end
    job_max = max(job)
    while begin <= end:
        mid = int((begin + end) / 2)
        if mid >= job_max and is_valid(mid, K, job):
            res = min(res, mid)
            end = mid - 1
        else:
            begin = mid + 1
    return res * T


job = [12, 6, 9, 15, 5, 9]
k = 4
T = 5
print(get_minimum_time(k, T, job))

入力

4, 5, [12, 6, 9, 15, 5, 9]

出力

75

計算量

二分探索は O(log Σjob) 回繰り返され、各判定 is_valid() は O(n) で動作するため、全体の計算量は O(n log Σjob) となります。すべての割り当てパターンを試す総当たり法に比べて非常に効率的で、ジョブ数や合計時間が大きい場合でも実用的に動作します。