Job Sequencing Problem

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:

Output:

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:

Output:

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:

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:

1. Sort the jobs in the descending order of the profits
2. Create an array of size s, where s = maximum deadline among all the jobs
3. Initialize the array with -1, since, we have not scheduled any job initially.
4. 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
5. 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
6. 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:

Java Implementation

Below given is the Java code for the Job Sequencing problem :

Python Implementation

Below given is the Python code for the Job Sequencing problem:

Output:

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 --

1. Sorting the jobs on the basis of the maximum profit
2. 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 savior in this situation. That is, by using the Priority Queue - (max heap).

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:

Java Implementation

Below given is the Java implementation of the Job Sequencing problem.

Python Implementation

Now let us implement the above approach in Python. Here we can find the nearest Slot i, so that the $i$ 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.

Output:

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.