C++ এ প্রদত্ত সীমাবদ্ধতার সাথে সমস্ত কাজ শেষ করার জন্য সর্বনিম্ন সময় খুঁজুন

ধারণা

বিভিন্ন সময়ের প্রয়োজনীয়তার সাথে একটি প্রদত্ত কাজের ক্ষেত্রে, সেখানে k অভিন্ন অ্যাসাইনি উপলব্ধ রয়েছে এবং একজন অ্যাসাইনি কাজের এক ইউনিট করতে কতটা সময় নেয় তাও আমাদের দেওয়া হয়। আমাদের কাজ হল নিম্নোক্ত সীমাবদ্ধতা সহ সমস্ত কাজ সম্পূর্ণ করার সর্বনিম্ন সময় নির্ধারণ করা।

প্রথম সীমাবদ্ধতা হল একজন অ্যাসাইনিকে শুধুমাত্র সংলগ্ন কাজ দেওয়া যেতে পারে।

এখানে, উদাহরণস্বরূপ, একজন অ্যাসাইনিকে পজিশন 1 এবং 2-এ কাজ দেওয়া যেতে পারে, কিন্তু একটি অ্যারেতে অবস্থান 3-এ নয়৷
দ্বিতীয় সীমাবদ্ধতা হল যে দুজন অ্যাসাইনি একটি কাজ ভাগ করে নিতে (বা সহ-অর্পণ) করতে পারে না, অর্থাৎ, একটি কাজ আংশিকভাবে একজন অ্যাসাইনিকে এবং আংশিকভাবে অন্যকে দেওয়া যায় না৷

ইনপুট

k − উপলব্ধ অ্যাসাইনিদের সংখ্যা নির্দেশ করে।

t − কাজের একটি ইউনিট শেষ করতে একজন অ্যাসাইনীর যে সময় লাগে তা নির্দেশ করে

চাকরি[] - একটি অ্যারে নির্দেশ করে যা বিভিন্ন কাজের সময়ের প্রয়োজনীয়তা উপস্থাপন করে।

ইনপুট

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()) যা আমাদের নির্দেশ করে যে একটি নির্দিষ্ট সময়ের মধ্যে সমস্ত কাজ সম্পূর্ণ করা সম্ভব এবং উপলভ্য নিয়োগকারীদের সংখ্যা। এখানে, আমরা উত্তরের জন্য একটি বাইনারি অনুসন্ধান করে এই সমস্যার সমাধান করতে সক্ষম। দেখা গেছে বাইনারি সার্চের মিডল পয়েন্ট সম্ভব না হলে দ্বিতীয়ার্ধে সার্চ করুন, অন্যথায় প্রথমার্ধে সার্চ করুন। ক্ষুদ্রতম সময়ের জন্য বাইনারি অনুসন্ধানের জন্য নিম্ন সীমা 0 হিসাবে সেট করা যেতে পারে। এখানে, সমস্ত প্রদত্ত কাজের সময় যোগ করে উপরের সীমাটি পাওয়া যেতে পারে।

বর্তমানে প্রশ্ন উঠেছে কিভাবে isPossible() বাস্তবায়ন করা যায়। আমরা লোভী দৃষ্টিভঙ্গি ব্যবহার করে এই ফাংশন বাস্তবায়ন করতে পারি। কারণ আমরা জানতে চাই যে নির্দিষ্ট সময়ের মধ্যে সমস্ত কাজ শেষ করা সম্ভব কিনা, আমরা সমস্ত কাজের মাধ্যমে পরিদর্শন করি এবং বর্তমান অ্যাসাইনিকে একের পর এক কাজ বরাদ্দ করা বজায় রাখি। একই সময়ে, আমাদের মনে রাখা উচিত যে নির্দিষ্ট সময়ের মধ্যে একটি কাজ বরাদ্দ করা যেতে পারে। সেই মুহুর্তে, যখন বর্তমান অ্যাসাইনিটির নেওয়া সময় প্রদত্ত সময়ের অতিক্রম করে, তখন একটি নতুন অ্যাসাইনি তৈরি করুন এবং তাকে কাজ বরাদ্দ করা শুরু করুন। এটা দেখা গেছে যে অ্যাসাইনীর সংখ্যা বেশি হলে ধন্যবাদ, মিথ্যা ফেরত দিন, অন্যথায় সত্য ফেরত দিন।

উদাহরণ

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