বিভিন্ন জবের একটি তালিকা দেওয়া আছে, প্রতিটি জবের শুরু করার সময়, শেষ করার সময় এবং লাভও দেওয়া আছে। আমাদের কাজ হল জবের একটি সাবসেট খুঁজে বের করা যেখানে লাভ সর্বোচ্চ এবং কোনো দুটি জব একে অপরের সাথে ওভারল্যাপ করে না।
এই অ্যালগরিদমে সাব-প্রব্লেমের ফলাফল সংরক্ষণের জন্য একটি টেবিল ব্যবহার করা হয় এবং সাবপ্রব্লেমের ফলাফল ব্যবহার করে পুরো সমস্যা বটম-আপ পদ্ধতিতে সমাধান করা হয়।
এই অ্যালগরিদমের টাইম কমপ্লেক্সিটি O(n²), কিন্তু বাইনারি সার্চ ব্যবহার করে নন-কনফ্লিক্টিং জব খুঁজে বের করলে O(n log n) করা যায়।
ইনপুট এবং আউটপুট
ইনপুট: কিছু জবের শুরু, শেষ এবং লাভ ম্যাট্রিক্স রূপে। এবং জব সংখ্যা। এখানে ৪টি জব। 3 5 25 1 2 50 6 15 75 2 100 100 আউটপুট: সর্বোচ্চ লাভ ১৫০। জব সিকোয়েন্স: জব ২, জব ৪, অথবা জব ২, জব ১, জব ৩। দুটি কেসেই সর্বোচ্চ লাভ ১৫০।
অ্যালগরিদম
findMaxProfit(jobList, n)
ইনপুট: জব তালিকা এবং জব সংখ্যা।
আউটপুট: জব থেকে সর্বোচ্চ লাভ।
শুরু
জব তালিকাকে তাদের শেষ করার সময় অনুযায়ী সর্ট করুন
ফলাফল সংরক্ষণের জন্য টেবিল সংজ্ঞায়িত করুন
table[0] := jobList[0].profit
i := 1 থেকে n-1 পর্যন্ত, করুন
addProfit := jobList[i].profit
nonConflict := অন্য জবের সাথে কনফ্লিক্ট না করে এমন জব খুঁজুন
যদি কোনো নন-কনফ্লিক্টিং জব পাওয়া যায়, তবে
addProfit := addProfit + table[nonConflict]
যদি addProfit > table[i-1] হয়, তবে
table[i] := addProfit
অন্যথায়
table[i] := table[i-1]
끝난
result := table[n-1]
result ফেরত দিন
শেষ
উদাহরণ (C++)
#include <iostream>
#include <algorithm>
using namespace std;
struct Job {
int start, end, profit;
};
bool comp(Job job1, Job job2) {
return (job1.end < job2.end);
}
int nonConflictJob(Job jobList[], int i) {
for (int j=i-1; j>=0; j--) {
if (jobList[j].end <= jobList[i].start)
return j;
}
return -1;
}
int findMaxProfit(Job jobList[], int n) {
sort(jobList, jobList+n, comp);
int *table = new int[n];
table[0] = jobList[0].profit;
for (int i=1; i table[i-1]) ? addProfit : table[i-1];
}
int result = table[n-1];
delete[] table;
return result;
}
int main() {
Job jobList[] = {
{3, 5, 25},
{1, 2, 50},
{6, 15, 75},
{2, 100, 100}
};
int n = 4;
cout << "The maximum profit: " << findMaxProfit(jobList, n);
return 0;
}
আউটপুট
The maximum profit: 150
