इस समस्या में, हमें n तत्वों और aninteger h से मिलकर एक array arr[] दिया जाता है। सरणी के प्रत्येक तत्व arr[] में व्यक्ति के लिए लंबित कार्यों की संख्या होती है और H कार्य को पूरा करने के लिए शेष समय (घंटे में) है। हमारा कार्य सभी कार्यों को पूरा करने के लिए न्यूनतम गति ज्ञात करना है।
समस्या का विवरण :सरणी में दिए गए सभी कार्यों को H घंटे में पूरा करने के लिए हमें एक घंटे में व्यक्ति को जितने काम पूरे करने हैं, उतने कामों को पूरा करने की जरूरत है। अगर वह एक घंटे से भी कम समय में एआर [i] पर निर्दिष्ट सभी को पूरा कर सकता है, तो हम बाकी समय के लिए आदर्श रूप से बैठेंगे और घंटे के अंत के बाद, नौकरियों के अगले सेट पर चले जाएंगे।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
arr[] = {4, 5, 1, 7, 8}, H = 5 आउटपुट
8
स्पष्टीकरण
व्यक्ति को 5 घंटे में काम के 5 सेट पूरे करने होंगे। इसलिए, उसे 1 घंटे में अधिकतम नौकरियों के साथ सेट पर प्रदर्शन करना होगा जो उसकी गति होगी।
समाधान दृष्टिकोण
समस्या को हल करने के लिए, हमें वह न्यूनतम गति ज्ञात करनी होगी जिसके साथ वह सभी कार्यों को कर सके। तो, हम पहला मान पाएंगे जिसके लिए व्यक्ति सभी कार्यों को कर सकता है वह दिया गया समय है।
हम 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 mi = start + (end - start) / 2;
if (!canDoJobInTime(A, n, H, mi))
start = mi + 1;
else
end = mi;
}
return start;
}
int main() {
int A[] = { 3, 6, 7, 11 }, H = 8;
int n = sizeof(A) / sizeof(A[0]);
cout<<"The minimum speed to finish all jobs in time is "<<calcJobMinSpeed(A, n, H);
return 0;
} आउटपुट
The minimum speed to finish all jobs in time is 4