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}

. असाइन करके मिलता है

विधि

अब अवधारणा बाइनरी सर्च को लागू करने की है। मान लें कि क्या हमारे पास एक फ़ंक्शन है (जैसे कि संभव है ()) जो हमें इंगित करता है कि क्या सभी कार्यों को एक निश्चित समय और उपलब्ध असाइनरों की संख्या के भीतर पूरा करना संभव है। यहां, हम उत्तर के लिए द्विआधारी खोज करके इस समस्या को हल करने में सक्षम हैं। ऐसा देखा गया है कि यदि बाइनरी सर्च का मध्य बिंदु संभव न हो तो सेकेंड हाफ में सर्च करें नहीं तो फर्स्ट हाफ में सर्च करें। बाइनरी सर्च के लिए कम से कम समय के लिए निचली सीमा को 0 के रूप में सेट किया जा सकता है। यहां, सभी प्रदान किए गए नौकरी के समय को जोड़कर ऊपरी सीमा प्राप्त की जा सकती है।

वर्तमान में यह प्रश्न उठता है कि isPosible() को कैसे कार्यान्वित किया जाए। हम लालची दृष्टिकोण का उपयोग करके इस कार्य को लागू कर सकते हैं। क्योंकि हम जानना चाहते हैं कि क्या एक निश्चित समय के भीतर सभी कार्यों को पूरा करना संभव है, हम सभी नौकरियों का दौरा करते हैं और वर्तमान असाइनी को एक-एक करके कार्य सौंपते रहते हैं। साथ ही हमें यह भी याद रखना चाहिए कि दी गई समय सीमा के भीतर कोई काम सौंपा जा सकता है। उस समय, जब वर्तमान समनुदेशिती द्वारा लिया गया समय दिए गए समय को पार कर जाता है, तो एक नया समनुदेशिती उत्पन्न करें और उसे कार्य सौंपना शुरू करें। यह देखा गया है कि यदि असाइन करने वालों की संख्या अधिक धन्यवाद हो जाती है, तो झूठी वापसी करें, अन्यथा सत्य लौटें।

उदाहरण

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