Tìm thời gian tối thiểu để hoàn thành tất cả các công việc với các ràng buộc nhất định trong C ++

Khái niệm

Đối với một loạt công việc nhất định với các yêu cầu thời gian khác nhau, có k người được giao giống hệt nhau và chúng tôi cũng được cung cấp thời gian mà một người được giao dành hết thời gian để hoàn thành một công việc. Nhiệm vụ của chúng tôi là xác định thời gian tối thiểu để hoàn thành tất cả các công việc với các giới thiệu sau.

Ràng buộc đầu tiên là người được giao chỉ có thể được giao các công việc liền kề.

Ví dụ:ở đây, một người được giao có thể được giao công việc ở vị trí 1 và 2, nhưng không phải ở vị trí 3, trong một mảng.
Ràng buộc thứ hai là hai người được giao không thể chia sẻ (hoặc đồng giao) một công việc, nghĩa là không thể giao một phần công việc cho một người được giao và một phần cho người khác.

Đầu vào

k - Cho biết số lượng người được chỉ định có sẵn.

t - Cho biết thời gian người được giao hoàn thành một công việc đơn lẻ

JOB [] - Chỉ ra một mảng thể hiện yêu cầu về thời gian của các công việc khác nhau.

Đầu vào

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

Đầu ra

Ở đây, thời gian tối thiểu cần thiết để hoàn thành tất cả các công việc là 48.

Có sẵn 2 người được giao. Chúng tôi có được thời gian này bằng cách chỉ định {5, 6} cho người được chuyển nhượng đầu tiên và {12} cho người được chuyển nhượng thứ hai.

Đầu vào

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

Đầu ra

Chúng tôi có được thời gian này bằng cách chỉ định {12} {6, 9} {15} và {5, 9}

Phương pháp

Bây giờ khái niệm là thực hiện Tìm kiếm nhị phân. Giả sử nếu chúng ta có một hàm (giả sử isPossible ()) thông báo cho chúng ta biết liệu chúng ta có thể hoàn thành tất cả các công việc trong một thời gian nhất định và số lượng nhân viên khả dụng hay không. Ở đây, chúng tôi có thể giải quyết vấn đề này bằng cách thực hiện tìm kiếm nhị phân cho câu trả lời. Người ta đã thấy rằng nếu điểm giữa của tìm kiếm nhị phân không thể thực hiện được thì hãy tìm kiếm trong nửa sau, nếu không thì tìm kiếm trong nửa đầu. Giới hạn dưới cho Tìm kiếm nhị phân cho thời gian nhỏ nhất có thể được đặt là 0. Ở đây, giới hạn trên có thể nhận được bằng cách thêm tất cả thời gian công việc được cung cấp.

Hiện tại, câu hỏi được đặt ra là làm thế nào để triển khai isPossible (). Chúng ta có thể thực hiện chức năng này bằng cách sử dụng Phương pháp tiếp cận Tham lam. Bởi vì chúng tôi muốn biết liệu có thể hoàn thành tất cả các công việc trong thời gian sớm nhất hay không, chúng tôi sẽ xem qua tất cả các công việc và duy trì giao từng công việc cho người được giao hiện tại. Đồng thời, chúng ta nên nhớ rằng một công việc có thể được giao trong thời hạn nhất định. Vào thời điểm đó, khi thời gian của người được giao hiện tại vượt qua thời gian đã cho, hãy tạo một người được giao mới và bắt đầu giao việc cho người đó. Người ta thấy rằng nếu số lượng người được chỉ định trở nên cảm ơn nhiều hơn, thì trả về false, nếu không thì trả về true.

Ví dụ

// 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;
}