Maximum Profit In Job Scheduling

Solution Approach 

The most brute idea is to try out all the subsets and find the maximum profit among them. But this will have an exponential time complexity which is, we’re sure, not required here. 

We know that the set of jobs, let’s say S, that will give the maximum profit is undoubtedly a subset of the assigned n jobs. If we talk about some nth job, this nth job will either be in the set S or not. 

• Now, if the nth job is not in S, then our search space kind of gets reduced till n-1 only, and now we’ve to find the answer for the jobs 1 to n-1 only. 

1,2,3,4,.....,n get reduced to 1,2,3,....,n-1 as n doesn’t contribute to the answer. Therefore, it can be neglected.

• If the nth job is in S, then we know that all jobs whose end days are greater than or equal to the start day of the nth job can’t be there in S. So, now the next job included will be the largest i from the 1(let’s say j) which has end[j] <start[n]. In this case, now our search space gets reduced till j. And the total answer will be the (answer of jobs from 1 to j ) + profit[n]. 

So the discussion reduces to how to find that particular j?

What we can do is, find all the end days in a sorted vector and find it using the lower_bound function on that vector.

So, you can see that if we define dp[i] as the maximum possible profit from tasks 1 to i, the problem is solved. dp[0] will be 0 because no profit can be made from 0 tasks.

The solution involves a technique called dynamic programming. So, it’s suggested that you revise this topic once

Steps are: 

• Make a struct of jobs containing data of start day as “strt,” end day as “ed,” and profit as “profit.” 
• Declare a vector v of jobs of size n+1. Here, the size is n+1 because we’ll do the indexing starting from 1. 
• Take the n inputs and store them in the vector v. 
• Sort the vector v using a comparator that sorts the jobs in ascending order according to their end days.
• Declare the dp array of size n+1 and update dp[0] = 0;
• Declare a vector ends and push all the ends in this vector. It will be a sorted vector because we’re pushing from vector v, which is itself sorted according to the end days.
• Traverse from 1 to n.
  • If we don’t include/take the job in S, dp[i] depends on dp[i-1].
  • If we include/take it, it depends on dp[j] such that j is the largest index from 1 which has v[i].ed<v[i].strt. In this case, dp[i] = profit[i]+dp[j]. We’ll find this j using the findj() function which basically searches j using the lower_bound() function on ends vector for value v[i].strt. 
• Print the value of dp[n-1].

Implementation

Input

Output

Time complexity

O(nlogn), where n is the number of jobs.

Reason: Because we’re iterating through i=1 to i<n (which contributes O(n)) and O(logn) for finding j using the lower_bound() function, and it works based on binary search.

Space complexity

O(n), where n is the number of jobs.

Reason: We’re storing the values of dp for each i from 0 to n-1.

Frequently asked questions

What is the time complexity of the weighted job scheduling algorithm?

Answer: O(nlogn), where n is the number of jobs.

What is dynamic programming, and where is it used?

Answer: Dynamic programming is an optimization method used in various programming problems. It is used in problems where the solution depends on smaller overlapping subproblems. We use it to memorize the results so that they can easily be used later when needed.

What is a weighted job scheduling problem?

Answer: A problem in which we’ve to find the maximum profit earned by scheduling jobs such that only one job is done on one day is called the weighted job scheduling problem.

What are overlapping subproblems?

 Answer: A problem has overlapping subproblems if it can be divided into smaller subproblems that are reused multiple times.

Does dynamic programming have overlapping subproblems?

Answer:  Yes, dynamic programming is only used in problems where there are overlapping subproblems.

Where can I submit my “Maximum profit in job scheduling” code?

Answer: You can submit your code on Coding Ninjas Studio and get it accepted here right away.

Are there more Data Structures and Algorithms problems in Coding Ninjas Studio?

Answer: Yes, Coding Ninjas Studio is a platform that provides both practice coding questions and commonly asked interview questions. The more we’ll practice, the better our chances are of getting into a dream company of ours.

Key takeaways

In this article, we’ve discussed the maximum profit in the job scheduling problem. Here an effective method has been used, which is called dynamic programming. This is a crucial topic, and there are numerous exciting problems related to this topic. Some of these are 

Maximum profit, Longest Common prefix, wildcard pattern matching, and rod cutting problem. 

I would suggest you solve them to gain more confidence on this topic. These questions are asked during various coding contests as well as placements tests.

To practice more such problems, Coding Ninjas Studio is a one-stop destination. This platform will help you acquire effective coding techniques and give you an overview of student interview experience in various product-based companies.

Happy Coding!