Maximum Profit In Job Scheduling

Shreya Deep
Last Updated: May 13, 2022

Introduction

Scheduling jobs means that ordering them according to their start and end days in such a way that no two jobs are scheduled at the same time/day. If there is some profit associated with the jobs, we can find the maximum profit that can be earned by scheduling them most optimally.

In this article, we’ll learn how to find the maximum profit earned in job scheduling.

Let’s understand the problem statement in depth to get a better understanding.

Problem Statement

They are given n jobs with their starting day, ending day, and their profit. Schedule the jobs so that only one job is done on one day, and the profit earned by scheduling them is the maximum. Return the maximum profit. 

Note: You will be devoted to one job from its start day to end day, i.e., you can’t start any other task in between. 

For example: 

INPUT : n = 4 

  2 4 4

  3 6 6 

  6 8 2

  5 7 3

OUTPUT:  7

Explanation: Job 1 and Job 2 will coincide. Job 2 and Job 3 will again coincide on day 6. Job 3 and Job 4 will also coincide. But Job 1 and Job 4 won’t coincide and also give a profit of 7. 

Before directly jumping on Solution Approach, it’s recommended to try “Maximum Profit in Job Scheduling” on CodeStudio.

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

#include<iostream>
#include <bits/stdc++.h>
using namespace std;

struct job{
    int strt,ed,profit;
};

bool comp(job& j1,job& j2){
    return j1.ed<j2.ed;
}

int findj(vector<int>&ends, int strtofi){
    auto it = lower_bound(ends.begin(),ends.end(),strtofi);
    if(it==ends.begin()){
        return 0;
    }
    else{
        it--;
        return 1+(it-ends.begin());
    }
}

int main(){
    int n;
    cin>>n;
    vector<job>v(n+1);
    for(int i=1;i<n+1;i++){
        cin>>v[i].strt>>v[i].ed>>v[i].profit;
    }
    sort(v.begin()+1,v.end(),comp);
    int dp[n+1];
    dp[0] = 0;
    vector<int>ends;
    for(int i=1;i<v.size();i++){
        ends.push_back(v[i].ed);
    }
    for(int i=1;i<n;i++){
        int take = dp[i-1];
        int nottake = v[i].profit;
        int j = findj(ends,v[i].strt);
        nottake+=dp[j];
        dp[i] = max(take,nottake);
    }
    cout<<dp[n-1]<<endl;
    return 0;
}

 

Input

4

2 4 4

3 6 6

6 8 2

5 7 3

Output

7

 

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 CodeStudio and get it accepted here right away.

Are there more Data Structures and Algorithms problems in CodeStudio?

Answer: Yes, CodeStudio 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 profitLongest Common prefixwildcard 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, Codestudio 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!
 

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think