मान लीजिए हमारे पास N जॉब्स की एक सूची है जहां प्रत्येक जॉब के तीन पैरामीटर हैं। 1. प्रारंभ समय 2. समाप्ति समय 3. लाभ हमें जॉब्स का एक उपसमूह ढूंढना है जो अधिकतम लाभ से जुड़ा हो ताकि उपसमूह में कोई दो जॉब्स ओवरलैप न हों।
तो, यदि इनपुट N = 4 और J = {{2, 3, 55},{4, 6, 25},{7, 20, 150},{3, 150, 250}} जैसा है, तो आउटपुट [(2, 3, 55),(3, 150, 250)] और इष्टतम लाभ 305 होगा
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −
एक फ़ंक्शन find_no_conflict() परिभाषित करें, यह जॉब्स की एक सरणी, सूचकांक लेगा,
left := 0, right := index - 1
जब left <= right, तब तक करें −
mid := (left + right) / 2
यदि jobs[mid].finish <= jobs[index].start, तो −
यदि jobs[mid + 1].finish <= jobs[index].start, तो −
left := mid + 1
mid लौटाएं
mid लौटाएं
अन्यथा
right := mid - 1
-1 लौटाएं
मुख्य विधि से, निम्नलिखित करें −
समाप्ति समय के आधार पर जॉब_लिस्ट सरणी को सॉर्ट करें
जॉब्स के लिए n आकार की एक टेबल बनाएं जिसे टेबल कहा जाता है
table[0].value := job_list[0].profit
job_list[0] को table[0] के अंत में डालें
i := 1 से इनिशियलाइज़ करें, जब i < n, अपडेट करें (i को 1 से बढ़ाएं), तब तक करें −
include_profit := job_list[i].profit
l := find_no_conflict(job_list, i)
यदि l -1 के बराबर नहीं है, तो −
include_profit := include_profit + table[l].value
यदि include_profit > table[i - 1].value, तो −
table[i].value := include_profit
table[i].job := table[l].job
job_list[i] को table[i] के अंत में डालें
अन्यथा
table[i] := table[i - 1]
टेबल से जॉब्स प्रदर्शित करें
इष्टतम लाभ प्रदर्शित करें := table[n - 1].value
उदाहरण (C++)
बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें −
#include <bits/stdc++.h> using namespace std; class Job { public: int start, finish, profit; }; struct job_with_weight { vector<Job> job; int value; }; bool jobComparator(Job s1, Job s2) { return (s1.finish < s2.finish); } int find_no_conflict(Job jobs[], int index) { int left = 0, right = index - 1; while (left <= right) { int mid = (left + right) / 2; if (jobs[mid].finish <= jobs[index].start) { if (jobs[mid + 1].finish <= jobs[index].start) left = mid + 1; else return mid; } else right = mid - 1; } return -1; } int get_max_profit(Job job_list[], int n) { sort(job_list, job_list + n, jobComparator); job_with_weight table[n]; table[0].value = job_list[0].profit; table[0].job.push_back(job_list[0]); for (int i = 1; i < n; i++) { int include_profit = job_list[i].profit; int l = find_no_conflict(job_list, i); if (l != - 1) include_profit += table[l].value; if (include_profit > table[i - 1].value){ table[i].value = include_profit; table[i].job = table[l].job; table[i].job.push_back(job_list[i]); } else table[i] = table[i - 1]; } cout << "["; for (int i=0; i<table[n-1].job.size(); i++) { Job j = table[n-1].job[i]; cout << "(" << j.start << ", " << j.finish << ", " << j.profit << "),"; } cout << "]\nOptimal profit: " << table[n - 1].value; } int main() { Job arr[] = {{2, 3, 55},{4, 6, 25},{7, 20, 150},{3, 150, 250}}; int n = sizeof(arr)/sizeof(arr[0]); get_max_profit(arr, n); }इनपुट
{{2, 3, 55},{4, 6, 25},{7, 20, 150},{3, 150, 250}}आउटपुट
[(2, 3, 55),(3, 150, 250),] Optimal profit: 305