C++에서 주어진 제약 조건으로 모든 작업을 완료하는 데 필요한 최소 시간 찾기

<시간/>

컨셉

시간 요구 사항이 다른 주어진 작업 배열과 관련하여 사용할 수 있는 k개의 동일한 양수인이 있으며 양수인이 작업의 한 단위를 수행하는 데 소비하는 시간도 제공됩니다. 우리의 임무는 다음과 같은 제약 조건으로 모든 작업을 완료하는 데 필요한 최소 시간을 결정하는 것입니다.

첫 번째 제약은 양수인에게 연속 작업만 할당할 수 있다는 것입니다.

예를 들어, 양수인은 배열에서 위치 1과 2에 작업을 할당할 수 있지만 위치 3에는 할당할 수 없습니다.
두 번째 제약은 두 명의 담당자가 작업을 공유(또는 공동 할당)할 수 없다는 것입니다. 즉, 작업은 한 담당자에게 부분적으로 할당되고 다른 담당자에게는 부분적으로 할당될 수 없습니다.

입력

k - 사용 가능한 양수인의 수를 나타냅니다.

t - 담당자가 한 단위의 작업을 완료하는 데 걸린 시간을 나타냅니다.

JOB[] - 다른 작업의 시간 요구 사항을 나타내는 배열을 나타냅니다.

입력

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

출력

여기에서 모든 작업을 완료하는 데 필요한 최소 시간은 48시간입니다.

2명의 담당자가 있습니다. 첫 번째 양수인에게 {5, 6}을 할당하고 두 번째 양수인에게 {12}를 할당하여 이 시간을 얻습니다.

입력

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

출력

이번에는 {12} {6, 9} {15} 및 {5, 9}

를 할당하여 얻습니다.

방법

이제 개념은 이진 검색을 구현하는 것입니다. 주어진 시간과 사용 가능한 할당자 수 내에 모든 작업을 완료할 수 있는지 여부를 나타내는 함수(예:isPossible())가 있다고 가정합니다. 여기에서 답에 대한 이진 검색을 수행하여 이 문제를 해결할 수 있습니다. 이진 탐색의 중간 지점이 불가능하면 후반에서 탐색하고, 그렇지 않으면 전반에서 탐색하는 것으로 나타났습니다. 가장 작은 시간에 대한 Binary Search의 하한은 0으로 설정할 수 있습니다. 여기에서 상한은 제공된 모든 작업 시간을 더하여 얻을 수 있습니다.

현재 isPossible()을 구현하는 방법에 대한 질문이 제기되고 있습니다. Greedy Approach를 사용하여 이 기능을 구현할 수 있습니다. 주어진 시간 내에 모든 작업을 완료할 수 있는지 알고 싶기 때문에 모든 작업을 방문하여 현재 담당자에게 작업 할당을 하나씩 유지합니다. 동시에 주어진 시간 내에 작업을 할당할 수 있음을 기억해야 합니다. 그 순간 현재 양수인이 소요한 시간이 제공된 시간을 초과하면 새 양수인을 생성하고 작업 할당을 시작합니다. 양수인의 수가 더 많아지면 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;
}