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

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

what is Job sequencing with deadlines problem?

Suppose you are a freelancer who has got 5 different jobs to do which has a respective deadline and profit/payment. Also, it is unsure whether you will be able to complete all the jobs before the deadline of the respective job.

So, which job will you start working 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 the 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 the short deadline– In this case, It may happen that you had completed many jobs with short deadlines but you could have earned more if you have chosen the job which gives you max profit.

Here comes the greedy algorithm handy.

How to solve Job sequencing problem using the greedy algorithm?

Job Sequencing with Deadlines Algorithm

  1. Sort the jobs with respect to 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). Since 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 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 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 job with max profit) and lazy (completing job on the day of deadline).





Thats all for the job sequecing problem. If you have any problem then comment below.

Leave a Reply