Problem Statement
You are given a set of N jobs, where each job is having a deadline and a profit associated with it. You can only earn a profit if you complete the job within its given deadline. You can perform the job either before the deadline or strictly on the deadline, not after that.
Rules:
- Each job takes a single unit of time to execute
- Only one job can be performed at a given time
Input Format: The jobs will be provided in the form of (Job_id, deadline, profit) associated with that particular Job.
Task: Your task is to find the number of jobs done so as to earn the maximum profit.
Output Format: You are expected to print the number of jobs done and the maximum profit earned by doing them.
Examples
Let us see an example to see what our input and output format will look like.
Example 1:
Input:
N = 5
Jobs = [[1, 1, 10], [2, 5, 30], [3, 2, 15], [4,1,40], [5,2,20]]
Output:
The total number of jobs performed = 3, and the maximum profit = 90
Explanation:
In the above example, the job with job_id = 1 and job with job_id = 4, both have the same deadline, i.e. deadline = 1. As per the given rule, we can perform only one job at a time and within the given deadline. So, we choose the job with job_id = 4 since the profit associated with this job (profit = 40) is more than the one with job_id = 1 (profit = 10).
Next, we choose the job with job_id = 5 and take the profit = 30 associated with it.
Finally, we have two more jobs – job_id = 3 and job_id = 5 with the deadline as deadline = 2. So again, we choose the job that gives us maximum profit, i.e. profit = 20.
Total number of jobs done = 3 Maximum Profit = 40 + 30 + 20 = 90
Example 2:
Input:
N = 4
Jobs = [ [1,3,50], [2,1,15], [3,1,30], [4,1,5] ]
Output:
The total number of jobs performed = 2, and the maximum profit = 80
Explanation:
We choose the job with profit = 50. Then, out of three jobs with the same deadline (i.e. deadline = 1), we choose the job with maximum profit = 30. Total number of jobs done = 2 Maximum Profit = 50 + 30 = 80
Constraints
The constraints for the Job Sequencing problem are given below:
1 <= N <= 105
1 <= Deadline <= 100
1 <= Profit <= 500
Approach 1: Greedy Algorithm
The Job Sequencing problem wants us to find out the maximum profit we will gain by selecting the appropriate jobs within their deadlines. So, after reading the problem statement itself, a greedy approach comes up to our mind.
Just a recap of the Greedy Algorithm:-
Basically, the greedy algorithm deals with the solving of any problem in a greedy manner, i.e. by choosing the best option that is available for us at that particular moment. However, it is not concerned about the final results, i.e. whether our result will be optimal or not by choosing those options.
Strategy:
Our main goal should be to maximize the profit, which can be naturally done by choosing the jobs that give the highest profits.
But how can you efficiently choose the jobs with the highest profit? Well, that can be easily done by sorting the jobs in descending order of profit.
The next thing to note here is, that we must finish the job before or on its deadline. So, at max, we can perform a job on the day of its deadline, which is of utmost preferred. But why?
Because, that will leave some empty slots, which can be utilized later to perform other jobs in certain cases (especially when we have overlapping job deadlines).
Algorithm:
- Sort the jobs in the descending order of the profits
- Create an array of size s, where s = maximum deadline among all the jobs
- Initialize the array with -1, since, we have not scheduled any job initially.
- Run a for loop through every job and choose a slot i if:
- The job i can be performed on the day of its deadline
- Otherwise, loop from deadline -> 1 to find an empty slot where it can be performed
- If a slot is found, mark that slot with the job ID, increment the number of jobs perform, and add its profit to our answer
- Else, go to the next job
Implementation in Python, C++ and Java
C++ Implementation
Below given is the C++ code for the Job Sequencing problem :
Code:
#include<bits/stdc++.h>
#include <iostream>
#include <algorithm>
using namespace std;
// A structure to represent the jobs
// the job_id, deadline and the profit
struct Job {
int job_id;
int deadline;
int profit;
};
class Solution {
public:
// this function will compare the profits and return
// the job with higher profit
bool static comparison(Job a, Job b) {
return (a.profit > b.profit);
}
//Function to find the maximum profit and the number of jobs done
pair < int, int > JobScheduling(Job arr[], int n) {
sort(arr, arr + n, comparison);
int maximum_deadline = arr[0].deadline;
for (int i = 1; i < n; i++) {
maximum_deadline = max(maximum_deadline, arr[i].deadline);
}
int slot[maximum_deadline + 1];
for (int i = 0; i <= maximum_deadline; i++)
slot[i] = -1;
int countJobs = 0, jobProfit = 0;
for (int i = 0; i < n; i++) {
for (int j = arr[i].deadline; j > 0; j--) {
if (slot[j] == -1) {
slot[j] = i;
countJobs++;
jobProfit += arr[i].profit;
break;
}
}
}
return make_pair(countJobs, jobProfit);
}
};
int main() {
int n = 4;
Job arr[n] = {{1,3,50},{2,1,15},{3,1,30},{4,1,5}};
Solution ob;
//function call
pair < int, int > ans = ob.JobScheduling(arr, n);
cout << ans.first << " " << ans.second << endl;
return 0;
}
Java Implementation
Below given is the Java code for the Job Sequencing problem :
import java.io.*;
import java.lang.*;
import java.util.*;
class Job {
int id, profit, deadline;
Job(int x, int y, int z) {
this.id = x;
this.deadline = y;
this.profit = z;
}
}
class solve {
// return an array of size 2 having the 0th element equal to the count
// and 1st element equal to the maximum profit
int[] JobScheduling(Job arr[], int n) {
Arrays.sort(arr, (a, b) -> (b.profit - a.profit));
int maximum_deadline = 0;
for (int i = 0; i < n; i++) {
if (arr[i].deadline > maximum_deadline) {
maximum_deadline = arr[i].deadline;
}
}
int result[] = new int[maximum_deadline + 1];
for (int i = 1; i <= maximum_deadline; i++) {
result[i] = -1;
}
int num_of_jobs = 0;
int maximum_profit = 0;
for (int i = 0; i < n; i++) {
for (int j = arr[i].deadline; j > 0; j--) {
if (result[j] == -1) {
result[j] = i;
num_of_jobs++;
maximum_profit += arr[i].profit;
break;
}
}
}
int output[] = new int[2];
output[0] = num_of_jobs;
output[1] = maximum_profit;
return output;
}
}
class Main {
public static void main(String[] args) throws IOException {
//size of array
Job[] arr = new Job[4];
arr[0] = new Job(1, 4, 20);
arr[1] = new Job(2, 1, 10);
arr[2] = new Job(3, 2, 40);
arr[3] = new Job(4, 2, 30);
solve obj = new solve();
//function call
int[] answer = obj.JobScheduling(arr, 4);
System.out.println(answer[0] + " " + answer[1]);
}
}
Python Implementation
Below given is the Python code for the Job Sequencing problem:
class Solution:
def JobScheduling(self,Jobs,n):
#sort the jobs on the
# basis of profit in desc order
Jobs.sort(key = lambda a:a.profit, reverse = True)
maxm_deadline = 0
for i in range(n):
maxm_deadline = max(maxm_deadline, Jobs[i].deadline)
# The array size must be of the maxm deadline
arr = [-1]*(maxm_deadline+1)
profit, num_of_jobs = 0, 0
for i in range(n):
for j in range(Jobs[i].deadline,0,-1):
if arr[j] == -1:
arr[j] = Jobs[i].id
num_of_jobs += 1
profit += Jobs[i].profit
break
return [num_of_jobs,profit]
class Job:
def __init__(self,profit=0,deadline=0):
self.profit = profit
self.deadline = deadline
self.id = 0
if __name__ == '__main__':
ls = [[1,3,50], [2,1,15], [3,1,30], [4,1,5]]
n = len(ls)
Jobs = [Job() for i in range(n)]
for i in range(n):
Jobs[i].id = ls[i][0]
Jobs[i].deadline = ls[i][1]
Jobs[i].profit=ls[i][2]
ob = Solution()
ans = ob.JobScheduling(Jobs, 4)
print(ans[0], ans[1])
Output:
2 80
Time Complexity Analysis
Time Complexity Analysis
As we saw, using the above greedy approach, we are basically performing 2 operations in our given input to solve our job sequencing problem and get the maximum profit. They are as given below —
- Sorting the jobs on the basis of the maximum profit
- Running a loop through all the jobs -> Running another loop inside it from a particular deadline till we get an empty array cell.
So basically, in the first step, for sorting we will require $O(NlogN)$ time. And, for running a loop for $N$ jobs, we will need $O(N)$ time, also, within that, we are running another loop from the deadline till the first element (in the worst case). So for that, suppose we take $M$ time. Hence, the two loops together will take $O(N*M)$ time.
So, total time complexity = $O(NlogN)$ + $O(N*M)$
When M becomes greater than or equal to N, then we can say that the worst-case time complexity becomes $O$($N^2$)
Space Complexity Analysis
In this problem, we are using an array of the maximum size that is equal to the maximum deadline. Suppose the maximum deadline is $M$, so we will need an array of size $M$. Hence, the total space complexity becomes $O(M)$.
Approach 2 – Using Priority Queue
In the above greedy approach, we saw that our time complexity could get to $O(N^2)$ at the worst. But, hold on! we have another approach that could be our saviour in this situation. That is, by using the Priority Queue – (max heap).
But wait, what are priority queues?! Let’s recap 🙂
Basically, priority queues are special types of queues that have a priority attached to them. In simple words, the priority queue gives more priority to the elements with “high priority”. For example, it returns them before any low-priority elements. However in some implementations, if two or more elements have the same priority, then they will be returned in the order in which they were inserted (enqueued). Learn more about Priority Queues here in the scaler topics.
Algorithm
The basic approach that we will be using to solve this problem is, will sort the jobs based on the deadline and use a max heap to store the profit, deadline, and job ID of ith job. Let us note down the points we are going to take care which using the priority queue to solve our problem.
- Sort the array on the basis of their deadlines
- Calculate the slot between every two deadlines starting from the end of the array (our Jobs array). The slot calculated must be between consecutive deadlines.
- Include the
profits,deadlines, andjobIDsof each of the jobs in themax heap. - Now, till any of the slots are available and there are still jobs remaining in the
max heap, the result should include the ID of the job, as well as its deadline and maximum profit. So, keep on adding them. - In case you want to know the sequence in which the jobs are executed, then the Arrays of final output are sorted by their deadlines.
Implementing in C++, Java, Python
Let us see the code for each of them in Java, Python and C++.
C++ Implementation
Below given is the C++ code for the Job Sequencing problem.
Code:
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
// The below struct represents the
// the Job_Id, deadlines and the profit earned
// by a single job
struct Job {
char job_id;
int deadline;
int profit;
};
// below function calculateJobProfit is used for sorting
// all jobs according to their associated profits
struct calculateJobProfit {
bool operator()(Job const& x, Job const& y)
{
return (x.profit < y.profit);
}
};
// This function returns the maximum profit we will get from the jobs
// Also returns the order in which the jobs will be executed
void jobScheduling(Job arr[], int n)
{
int maximum_profit = 0;
vector<Job> output;
sort(arr, arr + n,
[](Job a, Job b) {
return a.deadline < b.deadline;
});
priority_queue<Job, vector<Job>, calculateJobProfit> pq;
for (int i = n - 1; i >= 0; i--) {
// to count the slot available between two jobs
int numOfSlotsAvailable;
if (i == 0) {
numOfSlotsAvailable = arr[i].deadline;
}
else {
numOfSlotsAvailable = arr[i].deadline - arr[i - 1].deadline;
}
// add the job profit (as a priority),
// the deadline and the job_id in maxHeap
pq.push(arr[i]);
while (numOfSlotsAvailable > 0 && pq.size() > 0) {
// get the job with the highest profit
Job job = pq.top();
maximum_profit += job.profit;
pq.pop();
// reduce the number of available slots
numOfSlotsAvailable--;
// add it to our output
output.push_back(job);
}
}
// sort the output based on their deadlines
sort(output.begin(), output.end(),
[&](Job x, Job y) {
return x.deadline < y.deadline;
}
);
cout << "The maximum profit obtained is = ";
cout << maximum_profit << ' ';
cout << endl;
cout << "The order in which jobs will be executed is:= "
"\n";
// print the result
for (int i = 0; i < output.size(); i++)
cout << output[i].job_id << ' ';
cout << endl;
}
int main()
{
// The driver code
Job arr[] = { { '1', 2, 100 },
{ '2', 1, 19 },
{ '3', 2, 27 },
{ '4', 1, 25 },
{ '5', 3, 15 } };
int n = sizeof(arr) / sizeof(arr[0]);
// calling our function
jobScheduling(arr, n);
return 0;
}
Output:
The maximum profit obtained is = 142
The order in which jobs will be executed is:=
1 3 5
Java Implementation
Below given is the Java code for the Job Sequencing problem.
Code:
// To calculate the maximum profit from the jobs
// and the order of the execution of the jobs
import java.util.*;
class Main {
static class Job {
char job_id;
int deadline;
int profit;
Job(char job_id, int deadline, int profit)
{
this.deadline = deadline;
this.job_id = job_id;
this.profit = profit;
}
}
static void jobScheduling(ArrayList<Job> arr)
{
// It sorts the job on the basis of the (maximum)deadlines
Collections.sort(arr, (x, y) -> {
return x.deadline - y.deadline;
});
int n = arr.size();
int max_profit = 0;
ArrayList<Job> output = new ArrayList<>();
PriorityQueue<Job> maxHeap = new PriorityQueue<>(
(a, b) -> { return b.profit - a.profit; });
// starting the iteration from the end
for (int i = n - 1; i > -1; i--) {
int slot_available;
// calculate slots between two deadlines
if (i == 0) {
slot_available = arr.get(i).deadline;
}
else {
slot_available = arr.get(i).deadline
- arr.get(i - 1).deadline;
}
maxHeap.add(arr.get(i));
while (slot_available > 0
&& maxHeap.size() > 0) {
// find the job with max_profit
Job job = maxHeap.remove();
max_profit += job.profit;
slot_available--;
output.add(job);
}
}
System.out.println("The maximum profit obtained from the jobs is := " + max_profit);
System.out.println();
// to get the order of the execution of jobs, sort them
// on the basis of their deadlines
Collections.sort(output, (a, b) -> {
return a.deadline - b.deadline;
});
System.out.println("The order in which jobs will be executed is:= ");
for (Job job : output) {
System.out.print(job.job_id + " ");
}
System.out.println();
}
// Out driver code
public static void main(String[] args)
{
ArrayList<Job> arr = new ArrayList<Job>();
arr.add(new Job('1', 2, 100));
arr.add(new Job('2', 1, 19));
arr.add(new Job('3', 2, 27));
arr.add(new Job('4', 1, 25));
arr.add(new Job('5', 3, 15));
// Calling our job scheduling function
jobScheduling(arr);
}
}
Output:
The maximum profit obtained from the jobs is := 142
The order in which jobs will be executed is:=
1 3 5
Python Implementation
Below given is the Python code for the Job Sequencing problem. A few important facts to note here are:
- Python library “heapq” does not have in-built support for maxheap, hence we only have the minheap in Python. But, we can use the “min-heap” in Python as a “max-heap” using simple logic. That is, while inserting the values in the heap if we want our heap to act as a max-heap, we can store the “negative” of the value on the basis of which we want our heap to sort. After that, while fetching the result, we will multiply it with a −1−1 so as to get back our original value. That will result in the minheap acting as a maxheap.
- In the below code, we have inserted the negative of the “Profits” in the heap, and while fetching the result, we have again taken the negative of the profit to get back our actual value.
- Doing so will result in making our min-heap act as a max-heap.
Code:
# Code to find the maximum profit
# and the number of jobs performed
# along with the sequence of the jobs
import heapq
"""
Jobs will be given in the order --
JobId, Job deadline , Job Profit
"""
def printJobScheduling(arr):
n, max_profit = len(arr), 0
# sorting on the basis of deadline
arr.sort(key=lambda x: x[1])
result = []
maxHeap = []
for i in range(n - 1, -1, -1):
if i == 0:
slots_available = arr[i][1]
else:
slots_available = arr[i][1] - arr[i - 1][1]
#storing the negative of profit so as to make our heap ac as a maxheap
heapq.heappush(maxHeap, (-arr[i][2], arr[i][1], arr[i][0]))
while slots_available and maxHeap:
profit, deadline, job_id = heapq.heappop(maxHeap)
max_profit += -profit
slots_available -= 1
# include the job in the result array
result.append([job_id, deadline, max_profit])
# to get the order in which the jobs will
# execute, we can sort the overall result
result.sort(key=lambda x: x[1])
print("The order in which jobs will be executed is:= ")
for job in result:
print(job[0], end=" ")
print("Maximum profit earned = ",max_profit )
# Our input for the code
arr = [[1, 2, 100],
[2, 1, 19],
[3, 2, 27],
[4, 1, 25],
[5, 3, 15]]
# Function Call
printJobScheduling(arr)
Output:
The order in which jobs will be executed is:=
1 3 5
Maximum profit earned = 142
Time Complexity Analysis
In this approach, we sort the array which approximately takes a time of O(NlogN). After that, we run a for loop in the backward order of the jobs. From that, we calculate the difference in the deadline and run a loop. The second loop will not run every time since it depends upon the slot available and whether there is an element in the heap or not. Also, we will insert the elements into the heap. Overall, the worst time complexity for these loops will be O(N). So, the total worst-case time complexity for our solution will be O(NlogN + N).
Space Complexity Analysis
In this problem, we are using the heap which will store all the NN elements in the worst case. Hence, the overall space complexity for the solution becomes O(N)
Approach 3 – Using Sets
In the first approach, we had to iterate through all the jobs for each job and find a job that supports the condition. And, we saw how our time complexity became quadratic – O($N^2$). Now, in this approach, we will learn how can we improve that using the sets.
Basically, we will apply the binary search on the sets and find the jobs which will satisfy the conditions.
Our algorithm for solving this problem will be as follows:
- Firstly, you need to sort the jobs based on the descending order of the profits.
- Then, find the maximum deadline for all the jobs
- Create a set, and initialize it with all the jobs in the descending order
- Now, iterate through the job and perform the following operations on it:
- If the set is empty, or the deadline of the current job is less than the last element in the set, simply do not do anything and ignore that job.
- Otherwise, apply the binary search and find the nearest slot ‘i’, for which i is less than the deadline, and add the profit.
- Also, increment the count of jobs and remove the ith element from the set.
- Finally, return the number of jobs and the maximum profit earned.
Implementation in C++, Java, and Python
C++ Implementation
Below given is the C++ implementation of the Job Sequencing problem.
Code:
// The input will be given as {{job.deadline, job.profit}}
//
// To compare the profits in the descending order
bool compare_profit(vector<int> &x, vector<int> &y)
{
return x[1] > y[1];
}
int jobScheduling(vector<vector<int>> &jobs)
{
sort(jobs.begin(), jobs.end(), compare_profit);
int maxm_Deadline = 0;
int maxm_Profit = 0;
set<int, greater<int>> slot;
for (int i = 0; i < jobs.size(); i++)
{
maxm_Deadline = max(maxm_Deadline, jobs[i][0]);
}
for (int i = maxm_Deadline; i > 0; i--)
{
slot.insert(i);
}
for (int i = 0; i < jobs.size(); i++)
{
if (slot.size() == 0 || jobs[i][0] < *slot.rbegin())
{
continue;
}
int available_slot = *slot.lower_bound(jobs[i][0]);
maxm_Profit = maxm_Profit + jobs[i][1];
slot.erase(available_slot);
}
return maxm_Profit;
}
Java Implementation
Below given is the Java implementation of the Job Sequencing problem.
// The job will contain the job deadline
// followed by the profit associated with the job
public static int job_Scheduling(int[][] jobs)
{
Arrays.sort(jobs, new Comparator<int[]>(){
public int compare(int[] x, int[] y)
{
if(x[1] < y[1]) return 1;
else return -1;
}
});
int maxm_Profit = 0;
int maxm_Deadline = 0;
TreeSet<Integer> set = new TreeSet<Integer>();
for (int i = 0; i < jobs.length; i++)
{
maxm_Deadline = Math.max(maxm_Deadline, jobs[i][0]);
}
for (int i = maxm_Deadline; i > 0; i--)
{
set.add(i);
}
TreeSet<Integer> slot = (TreeSet<Integer>)set.descendingSet();
for (int i = 0; i < jobs.length; i++)
{
if (slot.size() == 0 || jobs[i][0] < slot.last())
{
continue;
}
Integer available_slot = -1;
for (Integer value : slot)
{
if (value <= jobs[i][0])
{
available_slot = value;
break;
}
}
if (available_slot != -1)
{
maxm_Profit += jobs[i][1];
slot.remove(available_slot);
}
}
return maxm_Profit;
}
Python Implementation
Now let us implement the above approach in Python. Here we can find the nearest Slot i, so that the ii is less than the deadline by using the bisect in Python. The basic purpose of the bisect in Python is to find a position in the list where an element is to be inserted to keep the overall list sorted.
import bisect
"""
Input will be given in the below format:
[[JobID, JobDeadline, JobProfit]]
"""
def jobScheduling(jobs):
maxm_Profit = 0
maxm_Deadline = 0
slot = list()
# To sort on the basis of
# increasing profit and deadline
jobs.sort(key = lambda x: (-x[2], -x[1]))
# To find the maximum deadline
for i in range(0, len(jobs)):
maxm_Deadline = max(maxm_Deadline, jobs[i][1])
for x in range(1, maxm_Deadline + 1):
slot.append(x)
for i in range(len(jobs)):
if len(slot) == 0 or jobs[i][1] < slot[0]:
continue
available_slot = slot[bisect.bisect(slot, jobs[i][0]) - 1]
maxm_Profit = maxm_Profit + jobs[i][2]
slot.remove(available_slot)
return maxm_Profit
print(jobScheduling([[1,1,100],[2,1,20],[3,2,50],[4,2,10], [5,3,50]]))
Output:
200
Time Complexity Analysis
The worst-case time complexity for the above approach will be $O(NlogN)$. Since $O(NlogN)$ will be required for sorting. Apart from that, we run loops for different purposes like finding out the maximum deadline, and the available slot which takes $O(N)$.
Space Complexity
The worst-case time complexity will be $O(N)$. Because we are using an additional set.
Conclusion
In this article, we learned about the Job sequencing Problem and also the different approaches we used to calculate it. Let’s take a brief pause and reflect on what we have learned so far!
- In the Job Sequencing problem, we are provided with the Job ID, the deadline of the job, and the profit associated with it. We need to find out the maximum profit we will gain after completing the jobs within the given deadline.
- The first approach we used was using the greedy approach where we sorted the array on the basis of the profits and choose the elements that fell within the deadline, simultaneously calculating the profit for each.
- The second approach was using the priority queue where we inserted the Jobs in the maxheap, and we fetched the jobs based on the highest profit, using the slots. The slots were majorly responsible for keeping track of the difference between deadlines.
- The last approach was to use a set. It considerably improved the overall time complexity by
O(NlogN).
