এই সমস্যায়, আমাদেরকে একটি অ্যারে দেওয়া হয়েছে অ্যারে[] যা n উপাদান এবং aninteger h নিয়ে গঠিত। অ্যারে অ্যারের প্রতিটি উপাদানে ব্যক্তির জন্য মুলতুবি থাকা কাজের সংখ্যা থাকে এবং H হল কাজগুলি সম্পূর্ণ করার জন্য বাকি সময় (ঘন্টাগুলিতে)। আমাদের কাজ হল সমস্ত কাজ শেষ করার জন্য সর্বনিম্ন গতি খুঁজে বের করা।
সমস্যা বর্ণনা :H ঘন্টার মধ্যে অ্যারেতে দেওয়া সমস্ত কাজ সম্পূর্ণ করার জন্য একজন ব্যক্তির এক ঘন্টার মধ্যে কতগুলি কাজ সম্পূর্ণ করতে হবে তা আমাদের খুঁজে বের করতে হবে। তিনি যদি এক ঘন্টারও কম সময়ের মধ্যে arr[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
