Job Sequencing Problem

The idea here is to follow a greedy approach that we should complete the job with the maximum profit in the nearest available slot within its deadline. So, we can sort the jobs in the decreasing order of their profit, and we can maintain a boolean array to keep track of the available slots. So, for each job, we traverse the array backward from the deadline associated with the job to 1, and if any of the slots are empty, we add this profit to the answer and increase our count, else we ignore this job.

Algorithm

• Sort the jobs array in descending order of the profit associated with each job. We can write our own comparator function to achieve this.
• Create the variable, ‘maxProfit’ and ‘numberOfJobs ’, and Initialize it to 0.
• Create a variable ‘maxDeadline’ and find the maximum available deadline among all the jobs.
• Create a boolean array named slots of size ‘maxDeadline’ and initialize all the elements to false.
• Run a loop from i = 0 to N and do:
  • Run a loop j = jobs[i].deadline to 1 and do:
    • If slots[j] == false, then
      • maxProfit = maxProfit + jobs[i].profit
      • numberOfJobs=numberOfJobs + 1.
      • Make slots[j] = true and break out of the loop.
• Return the numberOfJobs and maxProfit.

O(N * maxDeadline), where ‘N’ denotes the number of elements of the array “jobs,” and ‘maxDeadline’ is the maximum available deadline among all the jobs.

As for every index of the array “jobs”, we may have to search for all the indices of the array “slots”. Hence, the time complexity in the worst case will be O(N * maxDeadline).

O(maxDeadline), where ‘maxDeadline’ is the maximum available deadline among all the jobs.

The slots array/list has a size of maxDeadline.