C++で指定された制約を使用してすべてのジョブを完了するための最小時間を見つける

コンセプト

異なる時間要件を持つ特定の一連のジョブに関して、利用可能なk個の同一の担当者が存在し、担当者が1ユニットのジョブを実行するために消費する時間も提供されます。私たちの仕事は、次の制約ですべての仕事を完了するための最小時間を決定することです。

• 最初の制約は、担当者には連続したジョブのみを割り当てることができるということです。

  ここで、たとえば、担当者は、配列内の位置1と2でジョブを割り当てることができますが、位置3では割り当てることができません。

• 2番目の制約は、2人の譲受人がジョブを共有（または共同割り当て）できないことです。つまり、ジョブを1人の譲受人に部分的に割り当てたり、他の譲受人に部分的に割り当てたりすることはできません。

入力

k −利用可能な担当者の数を示します。

t −担当者が1単位の仕事を完了するのにかかる時間を示します

JOB[]-さまざまなジョブの時間要件を表す配列を示します。

入力

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

出力

48

ここでは、すべてのジョブを完了するために必要な最小時間は48です。

利用可能な2人の担当者がいます。今回は、{5、6}を最初の譲受人に割り当て、{12}を2番目の譲受人に割り当てることで取得します。

入力

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

出力

75

今回は、{12} {6、9} {15}と{5、9}

メソッド

ここでの概念は、二分探索を実装することです。指定された時間と利用可能な担当者の数内にすべてのジョブを完了することが可能かどうかを示す関数（たとえば、isPossible（））があるかどうかを想定します。ここでは、答えを二分探索することでこの問題を解決することができます。二分探索の中間点が不可能な場合は後半で検索し、そうでない場合は前半で検索することがわかっています。最短時間の二分探索の下限は0に設定できます。ここで、提供されたすべてのジョブ時間を加算することで上限を取得できます。

現在、isPossible（）を実装する方法について疑問が生じています。欲張りアプローチを使用してこの関数を実装できます。与えられた時間内にすべての仕事を終えることができるかどうか知りたいので、私たちはすべての仕事を訪問し、現在の譲受人に一つずつ仕事を割り当て続けます。同時に、指定された制限時間内にジョブを割り当てることができることを覚えておく必要があります。その時点で、現在の担当者が指定した時間を超えると、新しい担当者を生成し、それにジョブの割り当てを開始します。担当者の数が感謝の数を超える場合はfalseを返し、そうでない場合はtrueを返すことがわかっています。

例

// C++ program to find minimum time to finish all jobs with
// given number of assignees
#include<bits/stdc++.h>
using namespace std;
// Shows utility function to get maximum element in 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;
}
// Now returns true if it is possible to finish jobs1[] within
// given time 'time1'
bool isPossible(int time1, int K1, int job1[], int n1){
   // Here, cnt1 is count of current assignees required for jobs
   int cnt1 = 1;
   int curr_time1 = 0; // Indicates time assigned to current
   //assignee
   for (int i = 0; i < n1;){
      // Now if time assigned to current assignee exceeds max1,
      // increment count1 of assignees.
      if (curr_time1 + job1[i] > time1) {
         curr_time1 = 0;
         cnt1++;
      }
      else { // Else add time of job to current time and move
         // to next job.
         curr_time1 += job1[i];
         i++;
      }
   }
   //Now returns true if count is smaller than k
   return (cnt1 <= K1);
}
// Here, returns minimum time required to finish given array of
//jobs
// K1 --> number of assignees
// T1 --> Time required by every assignee to finish 1 unit
// n1 --> Number of jobs
int findMinTime(int K1, int T1, int job1[], int n1){
   // Used to set start and end for binary search
   // end provides an upper limit on time1
   int end1 = 0, start1 = 0;
   for (int i = 0; i < n1; ++i)
      end1 += job1[i];
   int ans1 = end1; // Used to initialize answer
   // Determine the job that takes maximum time
   int job_max1 = getMax(job1, n1);
   // Perform binary search for minimum feasible time
   while (start1 <= end1){
      int mid1 = (start1 + end1) / 2;
      // Now if it is possible to complete jobs in mid time
      if (mid1 >= job_max1 && isPossible(mid1, K1, job1, n1)){
         ans1 = min(ans1, mid1); // Used to update answer
         end1 = mid1 - 1;
      }
      else
         start1 = mid1 + 1;
   }
   return (ans1 * T1);
}
// Driver program
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