# Maximum Profit in Job Scheduling Leetcode Solution

Difficulty Level Hard
Array Binary Search Dynamic Programming SortingViews 276

## Problem Statement

The Maximum Profit in Job Scheduling LeetCode Solution – “Maximum Profit in Job Scheduling” states that you’re given n jobs where each job starts from startTime[i] and ends at endTime[i] and obtaining the profit of profit[i].

We need to return the maximum profit that we can have such that no two chosen jobs overlap. Also, if a job ends at a time x, then we can start another job at a time greater than or equal to x.

## Example: `Input:  startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]`
`Output: 120`

Explanation:

• If we choose the first and fourth jobs, we can get a profit of 120 and, this is the maximum profit we can get.
• Note that the first and fourth jobs can be done simultaneously since they don’t overlap.
`Input:  startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]`
`Output: 150`

Explanation:

• If we choose the first, fourth and fifth job, we’ll get the maximum profit of 150.
• Note that the subset chosen doesn’t overlap.

## Approach

### Idea:

1. The main idea to solve this problem is to use dynamic programming and binary search.
2. First of all, we need to sort the jobs in non-decreasing order of their ending time which will help in calculating the maximum profit easily through dynamic programming.
3. Let dp[i] = maximum profit we can have if we consider first i+1 jobs.
4. There are two cases for each index:
1. Choose the current job: If we choose the current job then, this job will start from its startTime[i]. So, the maximum profit we can have is the current profit + dp[j]. dp[j] is the largest index j such that endTime[j] is less than or equal to startTime[i] and j must be strictly less than i. Note that if a valid j exists, then dp[i] = current profit + dp[j] otherwise, dp[i] = current profit.
1. To calculate the largest index j such that endTime[i] is less than or equal to startTime[i] and j<i, perform the binary search to find the suitable index since the jobs are already sorted in non-decreasing order of their end time.
2. Don’t Choose the current job: In this case, dp[i] = dp[i-1].
5. We need to take the maximum of both the above cases for calculating the values for each index.
6. Our answer will be dp[n-1].

## Code

### Maximum Profit in Job Scheduling Leetcode C++ Solution:

```class Solution {
public:
int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
int n = startTime.size();
vector<vector<int>> jobs;
for(int i=0;i<n;i++){
jobs.push_back({startTime[i],endTime[i],profit[i]});
}
sort(jobs.begin(),jobs.end(),[&](const vector<int>& a,const vector<int>& b){
if(a==b){
return a < b;
}
return a < b;
});
vector<int> dp(n);
dp = jobs;
for(int i=1;i<n;i++){
dp[i] = dp[i-1];
int l = 0,r = i - 1,prev = 0;
while(l<=r){
int mid = (l+r)/2;
if(jobs[mid]<=jobs[i]){
prev = dp[mid];
l = mid + 1;
}
else{
r = mid - 1;
}
}
dp[i] = max(dp[i],jobs[i]+prev);
}
return dp[n-1];
}
};```

### Maximum Profit in Job Scheduling Leetcode Java Solution:

```class Solution {
public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
int n = startTime.length;
int[][] jobs = new int[n];
for(int i=0;i<n;i++){
jobs[i] = new int[] {startTime[i],endTime[i],profit[i]};
}
Arrays.sort(jobs,(a,b)->a-b);
int[] dp = new int[n];
dp = jobs;
for(int i=1;i<n;i++){
dp[i] = dp[i-1];
int l = 0,r = i - 1,prev = 0;
while(l<=r){
int mid = (l+r)/2;
if(jobs[mid]<=jobs[i]){
prev = dp[mid];
l = mid + 1;
}
else{
r = mid - 1;
}
}
dp[i] = Math.max(dp[i],jobs[i]+prev);
}
return dp[n-1];
}
}```

## Complexity Analysis for Maximum Profit in Job Scheduling Leetcode Solution

### Time Complexity

The time complexity of the above code is O(NlogN) since we traverse the entire input array once and for each index, we’re applying binary search. Here, N = size of the input array.

### Space Complexity

The space complexity of the above code is O(N). We’re using a linear array to store the computed values.

Translate »