সময়সীমার সাথে কাজের সিকোয়েন্সিং সমস্যা

এই সমস্যায়, দেওয়া চাকরির তালিকা আছে। তালিকায় প্রতিটি কাজের জন্য সময়সীমা এবং লাভও দেওয়া আছে। প্রতিটি কাজ একটি একক সময় নেবে, তাই একটি কাজের জন্য সর্বনিম্ন সময়সীমা হল 1। যদি একবারে শুধুমাত্র একটি কাজ নির্ধারিত করা যায়, তাহলে লাভ সর্বাধিক করুন।

এই সমস্যাটি সমাধান করার জন্য, কাজের সেটের সমস্ত উপসেট তৈরি করা হয় স্বতন্ত্র উপসেটটি সম্ভাব্য কিনা তা পরীক্ষা করার জন্য। এছাড়াও, তৈরি করা সমস্ত সম্ভাব্য উপসেটের জন্য সর্বাধিক লাভের উপর নজর রাখুন।

এই অ্যালগরিদমের সময় জটিলতা হল O(n^2)

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

Input:
A list of jobs with job id, deadline and profit. And the number of jobs n.
{('a', 2, 100), ('b', 1, 19), ('c', 2, 27), ('d', 1, 25), ('e', 3, 15)}
n = 5
Output:
Following is maximum profit sequence of job sequence: c a e

অ্যালগরিদম

jobSequence(jobList, n)

ইনপুট - চাকরির তালিকা এবং তালিকায় উপস্থিত চাকরির সংখ্যা।

আউটপুট - ক্রম, কিভাবে কাজ নেওয়া হয়।

Begin
   sort the jobs in jobList according to their profit create a list of job sequence and slot to track free time slots
   initially make all slots are free
   for all given jobs i do
      for all jobs in the list from ending of the list do
         if slot[j] is free then
            jobSequence[j] := i
            make slot[j] := fill
            break the loop
      done
   done

   for all slots when it is not free do
      print id of job using jobList[jobSequence[i]]
   done
End

উদাহরণ

#include<iostream>
#include<algorithm>
using namespace std;

struct Job {
   char id;
   int deadLine;
   int profit;
};

bool comp(Job j1, Job j2) {
   return (j1.profit > j2.profit);    //compare jobs based on profit
}

int min(int a, int b) {
   return (a<b)?a:b;
}

void jobSequence(Job jobList[], int n) {
   sort(jobList, jobList+n, comp);    //sort jobList on profit

   int jobSeq[n];     // To store result (Sequence of jobs)
   bool slot[n];      // To keep track of free time slots

   for (int i=0; i<n; i++)
      slot[i] = false; //initially all slots are free

   for (int i=0; i<n; i++) {    //for all given jobs
      for (int j=min(n, jobList[i].deadLine)-1; j>=0; j--) {   //search from last free slot
         if (slot[j]==false) {
            jobSeq[j] = i;   // Add this job to job sequence
            slot[j] = true;  // mark this slot as occupied
            break;
         }
      }
   }

   for (int i=0; i<n; i++)
      if (slot[i])
         cout << jobList[jobSeq[i]].id << " ";    //display the sequence
}

int main() {
   Job jobList[] = {{'a',2,100}, {'b',1,19}, {'c',2,27},{'d',1,25},{'e',3,15}};
   int n = 5;
   cout << "Following is maximum profit sequence of job sequence: ";
   jobSequence(jobList, n);
}

আউটপুট

Following is maximum profit sequence of job sequence: c a e