Last Updated: 12 Feb, 2021
Job Sequencing Problem
Moderate
Asked in companies
You are given a 'Nx3' 2-D array 'Jobs' describing 'N' jobs where 'Jobs[i][0]' denotes the id of 'i-th' job, 'Jobs[i][1]' denotes the deadline of 'i-th' job, and 'Jobs[i][2]' denotes the profit associated with 'i-th job'.
You will make a particular profit if you complete the job within the deadline associated with it. Each job takes 1 unit of time to be completed, and you can schedule only one job at a particular time.
Return the number of jobs to be done to get maximum profit.
Note :
If a particular job has a deadline 'x', it means that it needs to be completed at any time before 'x'.
Assume that the start time is 0.
For Example :
'N' = 3, Jobs = [[1, 1, 30], [2, 3, 40], [3, 2, 10]].
All the jobs have different deadlines. So we can complete all the jobs.
At time 0-1, Job 1 will complete.
At time 1-2, Job 3 will complete.
At time 2-3, Job 2 will complete.
So our answer is [3 80].
Input Format :
The first line contains a single integer 'N', denoting the number of elements of the array 'Jobs'.
Next 'N' lines contain three integers, id, deadline, and profit of the 'ith' job.
Output Format :
The only line contains the number of jobs to be done to get maximum profit and maximum profit.
Note :
You do not need to print anything. It has already been taken care of. Just implement the given function.
Approaches
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.
- If slots[j] == false, then
- Run a loop j = jobs[i].deadline to 1 and do:
- Return the numberOfJobs and maxProfit.
In the above approach, for each index in the jobs array, we may have to traverse a boolean array of slots of size maxDeadline. However, we can optimize the above approach by using a set and applying a binary search on the elements of the set. So, we store the elements from maxDeadline to 1 in the set. We traverse the jobs array, and for each job, we find the nearest element present in the set that is less than or equal to the deadline of that job. If such an element exists in the set, we add the profit to the answer, increase our count, and remove this element from the set.
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 two variables, maxProfit, and number of jobs. Initialize both of them to 0.
- Create a variable maxDeadline and find the maximum available deadline among all the jobs.
- Create a set named slots that store the elements in decreasing order. Insert all the elements from maxDeadline to 1 into the set.
- Run a loop from i = 0 to N and do:
- If the set is empty or jobs[i].deadline is less than the last element of the set, then we ignore this job as it can’t be completed and continue in the loop.
- Apply binary search on the set and find the nearest available slot that is less than or equal to jobs[i].deadline. Let’s name this as availableSlot.
- maxProfit = maxProfit + jobs[i].profit
- Increment numberOfJobs by 1.
- Remove the availableSlot from the set.
- Return the numberOfJobs and maxProfit.
Note that, there is no in-built lower_bound or upper_bound function associated with the set data structure in python. So, we can implement the above approach in python by using a segment tree.
Similar problems