C++で制約条件を満たしながら全ジョブを完了させる最短時間を求めるアルゴリズム

概要

それぞれ所要時間の異なるジョブの配列が与えられ、k人の同一の作業者が利用可能であり、さらに作業者がジョブ1単位を完了するのにかかる時間も分かっているものとします。このとき、以下の制約条件下で全ジョブを完了するための最小時間を求めるのが本問題の目的です。

制約条件

• 制約1: 1人の作業者に割り当てられるのは「連続した」ジョブのみです。
  例えば、配列内の位置1と位置2のジョブは同じ作業者に割り当てられますが、それとは別に位置3だけを同じ作業者に割り当てることはできません。

• 制約2: 複数の作業者が1つのジョブを分担することはできません。つまり、あるジョブを一人の作業者に部分的に、別の作業者にも部分的に割り当てることは許されません。

入力パラメータ

• k — 利用可能な作業者の人数
• t — 作業者がジョブ1単位を完了するのにかかる時間
• JOB[] — 各ジョブの所要時間を表す配列

実行例

例1

k = 2, t = 4, JOB[] = {5, 6, 12}

出力:

48

このケースでは、全ジョブの完了に必要な最小時間は48です。2人の作業者に対して、1人目に {5, 6} を、2人目に {12} を割り当てることでこの時間が達成できます。

例2

k = 4, t = 5, JOB[] = {12, 6, 9, 15, 5, 9}

出力:

75

こちらは、{12}、{6, 9}、{15}、{5, 9} のように4人に分割して割り当てることで、最小時間 75 が得られます。

解法のアプローチ:二分探索

この問題は二分探索(Binary Search)を用いて効率的に解くことができます。

まず、「与えられた時間内に、利用可能な作業者数で全ジョブを完了できるかどうか」を判定する関数 isPossible() が存在すると仮定します。この関数を使えば、答えそのものに対して二分探索を行えます。

• 二分探索の中間点(mid)で全ジョブの完了が不可能な場合は、探索範囲を後半へ移動します。
• 可能な場合は、より小さい実現可能な値が存在するかもしれないため、探索範囲を前半へ移動します。

探索範囲の下限は 0、上限は全ジョブの所要時間の合計(1人の作業者がすべてを担当する場合)として設定できます。

isPossible() の実装 ― 貪欲法

isPossible() の実装には貪欲法(Greedy Approach)が適しています。具体的な手順は以下の通りです。

1. すべてのジョブを先頭から順に走査し、現在の作業者へ1つずつジョブを割り当てていきます。
2. 現在の作業者の累積作業時間が制限時間を超えそうになった時点で、新しい作業者を用意し、そこへの割り当てを開始します。
3. 必要となった作業者の総数が k を超えた場合は false を返し、超えなければ true を返します。

C++による実装例

// C++プログラム:指定された作業者数で全ジョブを完了する最小時間を求める
#include<bits/stdc++.h>
using namespace std;

// job1[0..n1-1] の最大要素を取得するユーティリティ関数
int getMax(int arr1[], int n1){
    int result1 = arr1[0];
    for (int i=1; i<n1; i++)
        if (arr1[i] > result1)
            result1 = arr1[i];
    return result1;
}

// 与えられた時間 'time1' 内に jobs1[] を完了できるかどうかを返す
bool isPossible(int time1, int K1, int job1[], int n1){
    // cnt1 は現在必要な作業者の数
    int cnt1 = 1;
    int curr_time1 = 0; // 現在の作業者に割り当てた時間

    for (int i = 0; i < n1;){
        // 現在の作業者の時間が上限を超える場合は作業者数を増やす
        if (curr_time1 + job1[i] > time1) {
            curr_time1 = 0;
            cnt1++;
        }
        else { // そうでなければジョブの時間を加算し次のジョブへ
            curr_time1 += job1[i];
            i++;
        }
    }
    // 作業者数が k 以下なら true を返す
    return (cnt1 <= K1);
}

// 与えられたジョブ配列を完了するのに必要な最小時間を返す
// K1 --> 作業者の数
// T1 --> 各作業者が1単位を完了するのに必要な時間
// n1 --> ジョブの数
int findMinTime(int K1, int T1, int job1[], int n1){
    // 二分探索の start と end を設定(end は時間の上限)
    int end1 = 0, start1 = 0;
    for (int i = 0; i < n1; ++i)
        end1 += job1[i];

    int ans1 = end1; // 回答の初期化

    // 最も時間のかかるジョブを求める
    int job_max1 = getMax(job1, n1);

    // 実現可能な最小時間を二分探索で求める
    while (start1 <= end1){
        int mid1 = (start1 + end1) / 2;

        // mid 時間でジョブ完了が可能かどうか判定
        if (mid1 >= job_max1 && isPossible(mid1, K1, job1, n1)){
            ans1 = min(ans1, mid1); // 回答を更新
            end1 = mid1 - 1;
        }
        else
            start1 = mid1 + 1;
    }
    return (ans1 * T1);
}

// ドライバープログラム
int main(){
    int job1[] = {12, 6, 9, 15, 5, 9};
    // int job1[] = {5, 6, 12};
    int n1 = sizeof(job1)/sizeof(job1[0]);
    int k1=4, T1=5;
    // int k1=2, T1=4;
    cout << findMinTime(k1, T1, job1, n1) << endl;
    return 0;
}

出力

75

計算量の評価

• 時間計算量: 二分探索は O(log S)(S は全ジョブ時間の合計)回の判定を行い、各判定 isPossible() は O(n) で実行できるため、全体の時間計算量は O(n log S) となります。
• 空間計算量: 入力配列以外に追加のデータ構造を必要としないため、O(1) です。