अवधारणा
दिए गए विभिन्न समय आवश्यकताओं वाली नौकरियों की सरणी के संबंध में, k समान असाइनी उपलब्ध हैं और हमें यह भी दिया गया है कि एक असाइनी को नौकरी की एक इकाई करने में कितना समय लगता है। हमारा कार्य निम्नलिखित प्रतिबंधों के साथ सभी नौकरियों को पूरा करने का न्यूनतम समय निर्धारित करना है।
पहला प्रतिबंध यह है कि एक असाइनी को केवल सन्निहित नौकरियां सौंपी जा सकती हैं।
उदाहरण के लिए, एक असाइनी को सरणी में स्थिति 1 और 2 पर नौकरियां सौंपी जा सकती हैं, लेकिन स्थिति 3 पर नहीं।
दूसरा प्रतिबंध यह है कि दो असाइनी एक नौकरी को साझा (या सह-असाइन) नहीं कर सकते, इसका मतलब है कि एक नौकरी को आंशिक रूप से एक असाइनी को और आंशिक रूप से दूसरे को नहीं सौंपा जा सकता।
इनपुट
k - उपलब्ध असाइनी की संख्या दर्शाता है।
t - एक असाइनी द्वारा नौकरी की एक इकाई को पूरा करने में लगने वाला समय दर्शाता है
JOB[] - एक सरणी जो विभिन्न नौकरियों की समय आवश्यकताओं को दर्शाती है।
इनपुट
k = 2, t = 4, JOB[] = {5, 6, 12}
आउटपुट
48
यहां, सभी नौकरियों को पूरा करने के लिए आवश्यक न्यूनतम समय 48 है।
2 असाइनी उपलब्ध हैं। हम {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 से अधिक हो जाती है, तो गलत लौटाएं, अन्यथा सच लौटाएं।
उदाहरण
// दिए गए असाइनी की संख्या के साथ सभी नौकरियों को पूरा करने का न्यूनतम समय ढूंढने के लिए C++ प्रोग्राम #include<bits/stdc++.h> using namespace std; // 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; } // अब सच लौटाता है यदि jobs1[] को दिए गए समय 'time1' के भीतर पूरा करना संभव है bool isPossible(int time1, int K1, int job1[], int n1){ // यहां, cnt1 वर्तमान असाइनी की गिनती है जिन्हें नौकरियों के लिए आवश्यक है int cnt1 = 1; int curr_time1 = 0; // वर्तमान असाइनी को असाइन किया गया समय दर्शाता है for (int i = 0; i < n1;){ // अब यदि वर्तमान असाइनी को असाइन किया गया समय max1 से अधिक है, // असाइनी की गिनती बढ़ाएं। if (curr_time1 + job1[i] > time1) { curr_time1 = 0; cnt1++; } else { // अन्यथा नौकरी का समय वर्तमान समय में जोड़ें और अगली नौकरी पर जाएं। curr_time1 += job1[i]; i++; } } // अब सच लौटाएं यदि गिनती k से छोटी या बराबर है return (cnt1 <= K1); } // यहां, दी गई नौकरियों की सरणी को पूरा करने के लिए आवश्यक न्यूनतम समय लौटाता है // K1 --> असाइनी की संख्या // T1 --> प्रत्येक असाइनी द्वारा 1 इकाई पूरा करने के लिए आवश्यक समय // n1 --> नौकरियों की संख्या int findMinTime(int K1, int T1, int job1[], int n1){ // बाइनरी खोज के लिए प्रारंभ और अंत सेट करने के लिए उपयोग किया जाता है // अंत समय पर ऊपरी सीमा प्रदान करता है int end1 = 0, start1 = 0; for (int i = 0; i < n1; ++i) end1 += job1[i]; int ans1 = end1; // उत्तर प्रारंभ करने के लिए उपयोग किया जाता है // वह नौकरी ढूंढें जिसमें अधिकतम समय लगता है int job_max1 = getMax(job1, n1); // न्यूनतम संभव समय के लिए बाइनरी खोज करें while (start1 <= end1){ int mid1 = (start1 + end1) / 2; // अब यदि mid समय में नौकरियों को पूरा करना संभव है if (mid1 >= job_max1 && isPossible(mid1, K1, job1, n1)){ ans1 = min(ans1, mid1); // उत्तर अपडेट करने के लिए उपयोग किया जाता है end1 = mid1 - 1; } else start1 = mid1 + 1; } return (ans1 * T1); } // ड्राइवर प्रोग्राम 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