ওজনযুক্ত কাজের সময়সূচী

বিভিন্ন চাকরির একটি তালিকা দেওয়া হয়, শুরুর সময়, শেষের সময় এবং সেই চাকরির লাভও সেই চাকরিগুলির জন্য দেওয়া হয়। আমাদের কাজ হল চাকরির একটি উপসেট খুঁজে বের করা, যেখানে লাভ সর্বাধিক এবং কোনও কাজ একে অপরকে ওভারল্যাপ করছে না।

এই অ্যালগরিদমে, আমরা সাব-সমস্যাগুলির ফলাফলগুলি সংরক্ষণ করার জন্য একটি টেবিল ব্যবহার করি এবং উপ-সমস্যাগুলির ফলাফলগুলি ব্যবহার করে, পুরো সমস্যাটি নীচে-আপ পদ্ধতিতে সমাধান করা যেতে পারে৷

এই অ্যালগরিদমের সময় জটিলতা হল O(n^2), কিন্তু আমরা দ্বন্দ্বমূলক কাজ অনুসন্ধান করার জন্য একটি বাইনারি অনুসন্ধান পদ্ধতি ব্যবহার করে O(n Log n) এ পরিবর্তন করতে পারি।

ইনপুট এবং আউটপুট

Input:
The start time, finish time and profit of some jobs as matrix form. And number of jobs. Here 4 jobs are present.
3   5  25
1   2  50
6  15  75
2 100 100

Output:
The maximum profit 150.
The job sequence is job 2, job 4, or job 2, job 1, job 3. for both cases the max profit is 150 here.

অ্যালগরিদম

findMaxProfit(jobList, n)

ইনপুট: কাজের তালিকা এবং কাজের সংখ্যা।

আউটপুট: চাকরি থেকে সর্বোচ্চ লাভ।

Begin
   sort job list according to their ending time
   define table to store results
   table[0] := jobList[0].profit

   for i := 1 to n-1, do
      addProfit := jobList[i].profit
      nonConflict := find jobs which is not conflicting with others
      if any non-conflicting job found, then
         addProfit := addProfit + table[nonConflict]
      if addProfit > table[i - 1], then
         table[i] := addProfit
      else
         table[i] := table[i-1]
   done
   result := table[n-1]
   return result
End

উদাহরণ

#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) {       //non conflicting job of jobList[i]
   for (int j=i-1; j>=0; j--) {
      if (jobList[j].end <= jobList[i-1].start)
         return j;
   }
   return -1;
}

int findMaxProfit(Job jobList[], int n) {
   sort(jobList, jobList+n, comp);           //sort jobs based on the ending time

   int *table = new int[n];       //create jon table
   table[0] = jobList[0].profit;

   for (int i=1; i<n; i++) {
      // Find profit including the current job
      int addProfit = jobList[i].profit;
      int l = nonConflictJob(jobList, i);
      if (l != -1)
         addProfit += table[l];
      table[i] = (addProfit>table[i-1])?addProfit:table[i-1];       //find maximum
   }

   int result = table[n-1];
   delete[] table;                 //clear table from memory
   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