C++で全ジョブ完了に必要な最小速度を求めるアルゴリズム(二分探索)

この問題では、n個の要素からなる配列 arr[] と整数 h が与えられます。配列の各要素には、その人が処理すべき未完了ジョブの数が格納されており、H はジョブ完了までに残された時間(単位：時間)を表します。求めるのは、すべてのジョブを時間内に完了させるための最小速度(1時間あたりに処理できるジョブ数)です。

問題の概要

与えられた配列内のすべてのジョブを H 時間以内に完了させるために、その人が1時間あたりに処理すべきジョブ数を求めます。あるジョブセットが1時間以内に終わった場合、残りの時間は待機し、1時間が経過した時点で次のジョブセットへ移ります。

入力例

arr[] = {4, 5, 1, 7, 8}, H = 5

出力例

8

解説

この人は5つのジョブセットを5時間で完了する必要があります。したがって、最も多くのジョブを含むセット(8個)をちょうど1時間で処理できる速度が必要となり、答えは 8 になります。

解法のアプローチ

この問題を解くには、与えられた時間内にすべてのタスクを完了できる最小の速度を見つける必要があります。そのため、「条件を満たす最初の値」を探索することになります。

探索範囲は 1 から「最大のジョブ数」までです。この範囲は非常に大きくなる可能性があるため、計算量を抑えるために二分探索を利用します。

現在の候補速度 s で間に合うかどうかを判定するには、各ジョブセットの完了に必要な時間(切り上げ除算)を求めて合計します。合計時間が H 以下であれば「可能」、そうでなければ「不可能」と判断できます。

この判定を繰り返しながら二分探索を行うことで、全体の計算量は O(n log(max(arr))) に抑えられます。

C++による実装例

#include <bits/stdc++.h>
using namespace std;

// 指定した速度で時間内に全ジョブを完了できるかを判定
bool canDoJobInTime(int A[], int n, int H, int speed) {
    int timeTaken = 0;
    for (int i = 0; i < n; ++i)
        timeTaken += (A[i] - 1) / speed + 1; // 切り上げ除算で所要時間を計算
    return timeTaken <= H;
}

// 最小速度を二分探索で求める
int calcJobMinSpeed(int A[], int n, int H) {
    if (H < n)
        return -1; // 時間が足りない場合は不可能
    int maxJob = A[0];
    for (int i = 1; i < n; i++)
        maxJob = max(A[i], maxJob);
    int start = 1, end = maxJob;
    while (start < end) {
        int mi = start + (end - start) / 2;
        if (!canDoJobInTime(A, n, H, mi))
            start = mi + 1; // 間に合わない → 速度を上げる
        else
            end = mi;       // 間に合う → より小さい速度を探す
    }
    return start;
}

int main() {
    int A[] = { 3, 6, 7, 11 }, H = 8;
    int n = sizeof(A) / sizeof(A[0]);
    cout << "制限時間内に全ジョブを完了するための最小速度は "
         << calcJobMinSpeed(A, n, H);
    return 0;
}

出力

制限時間内に全ジョブを完了するための最小速度は 4

まとめ

本問題は「最小値の最大化・最大値の最小化」タイプの典型例であり、単調性のある判定条件に対して二分探索を適用することで効率的に解けます。ポイントは、切り上げ除算 (A[i] - 1) / speed + 1 を使って各セットの所要時間を正しく計算すること、そして探索範囲の上限を配列の最大値に設定することです。