Summary: In this tutorial, we will learn what the Job Sequencing with Deadlines Problem is and how to solve the Job Sequencing Problem in C, C++, and Java.

The problem of Job sequencing with deadlines can be easily solved using the greedy algorithm.

If you don’t know what is the Greedy algorithm then check this Fractional knapsack problem using the Greedy Algorithm, where I have explained the greedy algorithm with the examples.

What is Job Sequencing with Deadlines Problem?

Suppose you are a freelancer who has got 5 different jobs to do with the respective deadlines and profit/payment. Also, you are not sure whether you will be able to complete all the jobs before the respective deadlines.

So, which job will you start working on first?

  • The job which gives you maximum profit – In this case, the job may have a long deadline and by doing this job you may miss some jobs with a short deadline. And it can be unprofitable to you if the sum of profits from missed jobs is greater than the profit of the job which you are doing.
  • The job which has a short deadline – In this case, It may happen that you have completed multiple jobs within the given deadlines but there could be the possibility that you could have earned more if you would have chosen the job with max profit.

To solve the ambiguity of which job to choose, we use greedy approach.

Job Sequencing with Deadlines Solution using Greedy Algorithm

  1. Sort the jobs for their profit in descending order.
  2. Choose the uncompleted job with high profit (i.e. first job in the array, since the array is sorted). Because it is not necessary to complete the job on the very first date, we will do/complete the job on the last day of the deadline (i.e. Add the job to a new array/list at the index equal to its deadline day).
  3. Now again choose the next uncompleted high-profit job. Check its deadline. If its deadline is greater than the deadline of the previous chosen job, then we will do/complete this job on the last day of the deadline only if the day is empty, else will do the job on the previous empty day which is nearest to the deadline ( i.e. Add the job to new array/list at the index equal or nearest to its deadline day, only if the array is empty at particular index).
  4. If you don’t have the empty day before the job deadline (i.e. all the array index is occupied before the index=job.deadline) then do not do the job.
  5. Repeat the process for every job.
  6. The final array or list will give the best jobs to do for max profit.

In short, we are being greedy (choosing a job with max profit) and lazy (completing a job on the day of the deadline).

Here is the implementation of the steps in C, C++ and Java:

C

C++

Java

Output:

In this tutorial, we learned what the Job Sequencing with Deadlines Problem is and how to solve Job sequencing problem in C, C++, and Java programming languages.

Leave a Reply