使用 C++ 查找在给定约束条件下完成所有工作的最短时间

概念

对于给定的一组具有不同时间需求的工作，假设有 k 个相同的分配者可用，并且我们还提供了分配者完成一个工作单位需要的时间。我们的任务是在以下约束条件下确定完成所有工作的最短时间。

• 第一个约束是分配者只能分配连续的工作。

  例如，分配者可以分配数组中位置 1 和 2 的工作，但不能分配位置 3 的工作。

• 第二个约束是两个分配者不能共享（或共同分配）一个工作，这意味着一个工作不能部分分配给一个分配者，部分分配给另一个分配者。

输入

k - 表示可用的分配者数量。

t - 表示分配者完成一个工作单位所需的时间

JOB[] - 表示一个数组，表示不同工作的时限需求。

输入

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

输出

48

这里，完成所有工作所需的最短时间是 48。

有两个分配者可用。我们通过将 {5, 6} 分配给第一个分配者，将 {12} 分配给第二个分配者来获得此时间。

输入

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

输出

75

我们通过分配 {12} {6, 9} {15} 和 {5, 9} 来获得此时间

方法

现在，我们的思路是实现二分查找。假设我们有一个函数（例如 isPossible()），它告诉我们是否可以在给定的时间和可用分配者数量内完成所有工作。在这里，我们可以通过对答案进行二分查找来解决这个问题。我们观察到，如果二分查找的中点是不可能的，那么在后半部分搜索，否则在前半部分搜索。二分查找最小时间的下界可以设置为 0。在这里，上界可以通过添加所有给定的工作时间来获得。

现在问题出现了，如何实现 isPossible()。我们可以使用贪心算法实现此函数。因为我们想知道是否可以在给定的时间内完成所有工作，所以我们遍历所有工作，并维护逐个将工作分配给当前分配者。同时，我们应该记住，工作必须在给定的时间限制内完成。当当前分配者花费的时间超过提供的时间时，创建一个新的分配者并开始将工作分配给它。我们观察到，如果分配者的数量超过 k，则返回 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

Arnab Chakraborty

更新于: 2020-07-25

351 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习