এই সমস্যায়, আমাদের একটি অ্যারে arr[] দেওয়া আছে যাতে n সংখ্যক এলিমেন্ট আছে এবং একটি পূর্ণসংখ্যা h। অ্যারের প্রতিটি এলিমেন্টে ওই ব্যক্তির বাকি কাজের সংখ্যা আছে এবং H হল কাজ শেষ করার জন্য বাকি সময় (ঘণ্টায়)। আমাদের কাজ হল সব কাজ শেষ করার জন্য ন্যূনতম গতি খুঁজে বের করা।
সমস্যা বর্ণনা: আমাদের বের করতে হবে যে ব্যক্তিটি প্রতি ঘণ্টায় কতগুলো কাজ করতে পারলে arr[]-এ দেওয়া সব কাজ H ঘণ্টায় শেষ করতে পারবে। যদি সে arr[i]-এ নির্দিষ্ট কাজগুলো এক ঘণ্টার কম সময়ে শেষ করতে পারে, তবে বাকি সময় সে বসে থাকবে এবং এক ঘণ্টা শেষে পরের সেট অফ জবের तरफ যাবে।
উদাহরণ
ইনপুট
arr[] = {4, 5, 1, 7, 8}, H = 5
আউটপুট
8
ব্যাখ্যা
ব্যক্তিটি ৫ সেট কাজ ৫ ঘণ্টায় করতে হবে। সুতরাং, সে যেটিতে সবচেয়ে বেশি কাজ আছে সেটি ১ ঘণ্টায় করতে পারলে হবে, যা হবে তার গতি।
সমাধানের পদ্ধতি
সমস্যাটি সমাধানের জন্য, আমাদের ন্যূনতম গতি বের করতে হবে যাতে সে সব টাস্ক করতে পারে। সুতরাং, আমরা প্রথমে সেই মানটি খুঁজব যেটি সে দেওয়া সময়ে সব টাস্ক করতে পারবে।
আমরা গতির সার্চ রেঞ্জ ১ থেকে ম্যাক্স কাজের সংখ্যা পর্যন্ত রাখব। যেহেতু এই মান বড় হতে পারে, আমরা বাইনারি সার্চ ব্যবহার করব সহজ কম্পিউটেশনের জন্য।
চেক করতে জন্য, যদি বর্তমান গতি 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 << "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
