Job sequencing with deadlines in C++

In this tutorial, we will see how to solve Job sequencing with deadlines in C++. Initially, we will understand what the problem is and will solve it using the greedy method.

The Greedy method is a way to solve problems in which we always choose the next solution as the one which gives us the most obvious solution. In this way, we often neglect the efficient one. The Greedy method always gives us a locally optimal solution. Because it makes us select only the immediate best solution and not the globally one.

C++ for job sequencing with deadlines

For example, here we are given 5 tasks and when these tasks will be completed we will get a profit. So associated, with these jobs a profit is given. But that task must only be completed in that deadline to gain the profit. We have to identify the sequence of jobs which offer us the maximum profit. Every job takes a single unit of time for its completion.

Now to maximize the entire profit we will think this way. That we need to complete those jobs first which gives us the maximum profit but they must be completed in their deadline. So, it’s a maximization problem. We can solve it using the greedy method.

This is the data given to us:

Jobs               J1   J2   J3   J4   J5

Profits            20   15   10   5    1

Deadlines          2    2    1    3    3

 

Since the maximum deadline is 3. It means that no job is ready to wait beyond 3 hours for its completion. Now, if we apply the greedy method on it. We will arrange the jobs in decreasing profit. Now, let us pick the J1 with profit 20 and deadline 2. Since its deadline is 2 we can schedule it as below.

0------------1-----------------2------------3

                     J1

The Second highest job is J2. Now go to the 1-2 slot, it can wait till 2 hrs but the slot is already occupied. Now, we will see if any slots are available on the left side and yes it is. So, we assign it the 0-1 slot.

 

0------------1-----------------2------------3

     J2              J1

Now let us select the next job whose deadline is 1. Can we do this job? No, because our slot is already full so it is rejected.

Now the next job has a deadline of 3. So we will do this job.

0------------1-----------------2------------3

     J2             J1               J4

 

Now, for J5 we have no slots available so we will reject it.

That’s it, we have got our solution to the problem.

{J2,J1,J4} or {J1,J2,J4}

Total profit will be: 40

Algorithm for code

1) Sort all the jobs by decreasing order of profit.
2) Initializing the result sequence as the first job in sorted the jobs.
3) Do following for remaining n-1 jobs
a) If the current job can fit in the current slot without missing the deadline, add the current job to the result. Else reject the current job.

Implementation of the above algorithm with C++: Job sequencing with deadlines

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

// A structure to represent a job 
struct Job 
{ 
char id;	 
int dead; 
int profit; 
}; 

// This function is used for sorting all the jobs according to the profit 
bool compare(Job a, Job b) 
{ 
  return (a.profit > b.profit); 
} 


void jobschedule(Job arr[], int n) 
{ 
  // Sort all jobs according to decreasing order of prfit 
  sort(arr, arr+n, compare); 

  int result[n]; // To store result 
  bool slot[n];  

  // Initialize all slots to be free 
  for (int i=0; i<n; i++) 
    slot[i] = false; 


  for (int i=0; i<n; i++) 
  { 
  // Find a free slot for this job (Note that we start 
  // from the last possible slot) 
  for (int j=min(n, arr[i].dead)-1; j>=0; j--) 
  { 
    // Free slot found 
    if (slot[j]==false) 
    { 
      result[j] = i; // Add this job to result 
      slot[j] = true; // Make this slot occupied 
      break; 
    } 
  } 
  } 

  // Print the result 
  for (int i=0; i<n; i++) 
  if (slot[i]) 
    cout << arr[result[i]].id << " "; 
} 


int main() 
{ 
  Job arr[] = { {'a', 2, 20}, {'b', 2, 15}, {'c', 1, 10}, 
        {'d', 3, 5}, {'e', 3, 1}}; 
  int n = 5; 
  cout << "maximum profit sequence of jobs is-->"; 
  jobschedule(arr, n); 
   
} 

Output:

maximum profit sequence of jobs is-->b a d

Time complexity: o(n^2)

Also, refer to:

Count the number of occurrences of an element in a linked list in C++

Thank you!

2 responses to “Job sequencing with deadlines in C++”

  1. Maruf says:

    for (int j=min(n, arr[i].dead)-1; j>=0; j–)

    What did you mean by the loop ? More specifically, what did you mean by the iteration?

  2. Sakshi gupta says:

    @maruf
    By this loop, for(int i=0;i=0; j–)
    We are selecting the last possible slot we could find for our job. j is started from 5 for example and it is initially checking the last(fifth) slot of its free, then the fourth and so on …

Leave a Reply

Your email address will not be published. Required fields are marked *