C++ में सभी जॉब्स खत्म करने के लिए न्यूनतम गति ढूंढना

इस समस्या में, हमें n तत्वों वाला एक ऐरे arr[] और एक पूर्णांक h दिया गया है। ऐरे arr[] का प्रत्येक तत्व व्यक्ति के लिए लंबित जॉब्स की संख्या रखता है और H जॉब्स पूरा करने के लिए बचा समय है (घंटों में)। हमारा कार्य सभी जॉब्स को खत्म करने के लिए न्यूनतम गति ढूंढना है।

समस्या विवरण: हमें वह संख्या ढूंढनी है जो व्यक्ति को एक घंटे में पूरी करनी होगी ताकि ऐरे में दिए गए सभी जॉब्स H घंटों में पूरे हो जाएं। यदि वह arr[i] पर निर्दिष्ट सभी को एक घंटे से कम में पूरा कर सकता है, तो हम बाकी समय के लिए आदर्श रूप से बैठेंगे और घंटे के अंत में, अगले जॉब्स के सेट पर जाएंगे।

समस्या को समझने के लिए एक उदाहरण लेते हैं,

इनपुट

arr[] = {4, 5, 1, 7, 8}, H = 5

आउटपुट

8

व्याख्या

व्यक्ति को 5 घंटों में 5 जॉब्स के सेट पूरे करने हैं। इसलिए, उसे एक घंटे में अधिकतम जॉब्स वाले सेट को करने की आवश्यकता है जो उसकी गति होगी।

समाधान दृष्टिकोण

समस्या को हल करने के लिए, हमें वह न्यूनतम गति ढूंढनी होगी जिससे वह दिए गए समय में सभी कार्य कर सके। इसलिए, हम पहले उस मान को ढूंढेंगे जिसके लिए व्यक्ति दिए गए समय में सभी कार्य कर सकता है।

हम गति को 1 से एक बार में किए जाने वाले अधिकतम जॉब्स की संख्या की रेंज में खोजेंगे। चूंकि यह मान बड़ा हो सकता है, हम गणना में आसानी के लिए बाइनरी सर्च का उपयोग करेंगे।

जांचने के लिए, यदि वर्तमान गति s पर व्यक्ति समस्या हल कर सकता है, तो हम एक सेट को पूरा करने में लगे समय को ढूंढेंगे और फिर सभी सेट्स के लिए समय जोड़ेंगे। यदि यह समय H से कम है, तो यह संभव है अन्यथा नहीं।

हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम,

उदाहरण

#include <bits/stdc++.h>
using namespace std;

bool canDoJobInTime(int A[], int n, int H, int speed) {
   int timeTaken = 0;
   for (int i = 0; i < n; ++i)
      timeTaken += (A[i] - 1) / speed + 1;
   return timeTaken <= H;
}

int calcJobMinSpeed(int A[], int n, int H) {
   if (H < n)
      return -1;
   int maxJob = A[0];
   for (int i = 1; i < n; i++)
      maxJob = max(A[i], maxJob);
   
   int start = 1, end = maxJob;
   while (start < end) {
      int mid = start + (end - start) / 2;
      if (!canDoJobInTime(A, n, H, mid))
         start = mid + 1;
      else
         end = mid;
   }
   return start;
}

int main() {
   int A[] = {3, 6, 7, 11}, H = 8;
   int n = sizeof(A) / sizeof(A[0]);
   cout << "समय पर सभी जॉब्स खत्म करने के लिए न्यूनतम गति है " << calcJobMinSpeed(A, n, H);
   return 0;
}

आउटपुट

समय पर सभी जॉब्स खत्म करने के लिए न्यूनतम गति है 4

एल्गोरिथ्म विश्लेषण

• समय जटिलता: O(n log max_job)
• स्पेस जटिलता: O(1)
• बाइनरी सर्च रेंज: [1, max(arr)]
• प्रत्येक गति के लिए, O(n) में सत्यापन

मुख्य अंतर्दृष्टि

गति s पर, जॉब i को पूरा करने में ceil(arr[i]/s) घंटे लगते हैं। कुल समय सभी के लिए ceil(arr[i]/s) का योग है। हम न्यूनतम s चाहते हैं जहां कुल समय ≤ H हो।