Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

algorithms
communitycreator

What is Weighted Job Scheduling in Dynamic Programming?

Sankalp Kotewar

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Weighted Job Scheduling, or variants of it, is one of the most popular Dynamic Programming questions asked in interviews by many tech companies. This problem gives us a list of jobs with profits associated with each of them. You are required to return the maximum profit one can earn by scheduling these jobs one after the other.

The problem

You are given a list of n jobs with their start time, end time, and the profit you can earn by doing that job. Your task is to find the maximum profit you can earn by picking up some (or all) jobs, ensuring no two jobs overlap.

Note: If you choose a job that ends at time X, you will be able to start another job that starts at time X.

Input

You are given a 2D array jobs of size nx3 where:

 job[i] = {startTime, endTime, profit}

In addition, we also know the following information:

jobs[n][0]: 0th index gives you start time, with jobs[i][0] representing start time of ith job.

jobs[n][1]: 1st index gives you end time, with jobs[i][1] representing end time of ith job.

jobs[n][2]: 2nd index gives you the profit, with jobs[i][2] representing profit you can earn by finishing ith job.

Output

Return the maximum profit that you can obtain by executing <= n jobs, ensuring there’s no overlap between any jobs.

Example

Input

jobs = {{1, 6, 6}, {2, 5, 5}, {5, 7, 5}, {6, 8, 3}}

Output

10

Explanation

You can choose either a {1, 6, 6} and {6, 8, 3} combination or a {2, 5, 5} and {5, 7, 5} combination since these combinations do not overlap each other. The first combination returns you a profit of 9, whereas the second combination returns you a profit of 10. You have to return the maximum output, which is 10 in this example.

Approach

If you pay close attention, this is one of those problems where you have a choice to either pick a job or leave it. So for every job, you have a choice available.

Also, since the jobs are given in random order, we need to ensure that we first sort the array by either the startTime or the endTime, depending on how we want to solve this problem. If you decide to sort the array by startTime, your problem will start from 0th index, and if you decide to sort the array by endTime, the problem will start from the n-1th index. This way, you’ll have the jobs available to you in the sorted order, which helps us to minimize the efforts of accessing the next or the previous available job. To understand the solution, let’s start from the last index.

To begin with, we’ll sort the array in the increasing order of their end times.

Once we’ve sorted the array, we’ll iterate the array from n-1th index to 0th index. At every index, we’ll have a choice to either schedule the job or not.

Choice 1: Include the job at index i

int incl = jobs[i][2] + maximum profit we can get from jobs in range 0 to i-1 without conflicting

Choice 2: Exclude the job at index i

int excl = maximum profit we can earn from the remaining jobs

Given the choices above, we choose the option that gives us the maximum profit. So the final answer becomes:

int maximumProfit = max(incl, excl);

Let’s write the recursive code for what we’ve analyzed until now.

Solution

#include<bits/stdc++.h>
using namespace std;
// Function to find the index of the previous job whose end time is less than or equal to the current job's start time
int findPreviousNonConflictingJob(vector<vector<int>> jobs, int n) {
for (int i = n - 1; i >= 0; i--) {
if (jobs[i][1] <= jobs[n][0]) {
return i;
}
}
// return -1 if no non-conflicting job is found
return -1;
}
// A recursive function to find the maximum profit subset of non-overlapping jobs, which are sorted according to finish time
int findMaxProfit(vector<vector<int>> jobs, int index) {
if (index < 0) return 0; // base case
if (index == 0) return jobs[0][2]; // return profit in case of just one item
// find index of the last non-conflicting job with the current job
int prevNonConflictingIndex = findPreviousNonConflictingJob(jobs, index);
// Choice 1 - include the current job and find maximum profit for the jobs in range 0 to previous non-conflicting job index
int includeJob = jobs[index][2] + findMaxProfit(jobs, prevNonConflictingIndex);
// Choice 2 - exclude the current job and find maximum profit for the remaining jobs from index 0 to index-1
int excludeJob = findMaxProfit(jobs, index - 1);
// return the maximum profit obtained by either including or excluding the current job
return max(includeJob, excludeJob);
}
bool comparator(vector<int> a, vector<int> b) {
return a[1] == b[1] ? a[0] < b[0] : a[1] < b[1];
}
int main() {
vector<vector<int>> jobs{{0,6,60},{1,4,30},{3,5,10},{5,7,30},{5,9,50},{7,8,10}};
// sort jobs in increasing order of their finish times
sort(jobs.begin(), jobs.end(), comparator);
// we call findMaxProfit function iteratively starting from the last job
cout << "The maximum profit is " << findMaxProfit(jobs, jobs.size() - 1);
return 0;
}

The time complexity for the above solution is exponential though, since it is naive recursion. In case there are no overlaps, the findPreviousNonConflictingJob function will always return the i-1th index. So the worst case complexity for this scenario would be O(n*2n).

We need to now optimize our solution to bring down its runtime complexity. Now consider this situation when findPreviousNonConflictingJob() always returns the previous job, then findMaxProfit(arr, i-1) is called twice and the time complexity becomes O(n*2n). Similarly, when findPreviousNonConflictingJob() returns i-1th index, there are two recursive calls, for i-2 and i-1. This is similar to the Fibonacci overlapping subproblem.

So this problem has both properties of Dynamic Programming:

  • Optimal Substructure (optimal choice as explained above)
  • Overlapping Subproblems (Fibonacci overlapping explanation)

Another thing you should notice is that we have a sorted array, so linear search can be further reduced from O(n) to O(nlogn) by using binary search.

Below is the implementation after applying these optimizations:

#include<bits/stdc++.h>
using namespace std;
// Function to find the index of the previous job whose end time is less than or equal to the current job's start time
int findPreviousNonConflictingJob(vector<vector<int>> jobs, int n) {
// Binary search implementation
int low = 0;
int high = n;
while (low <= high){
int mid = (low + high) / 2;
if (jobs[mid][1] <= jobs[n][0]){
if (jobs[mid + 1][1] <= jobs[n][0]) low = mid + 1;
else return mid;
}
else high = mid - 1;
}
return -1; // return -1 if no non-conflicting job is found
}
int findMaxProfit(vector<vector<int>> jobs) {
int n = jobs.size();
int dp[n]; // dp[i] stores max profit for jobs from 0 till ith index
dp[0] = jobs[0][2]; //initializing array with base case, i.e. 1st job's profit
for (int i = 1; i < n; i++){
// find index of the last non-conflicting job with the current job
int prevNonConflictingIndex = findPreviousNonConflictingJob(jobs, i);
int currentProfit = jobs[i][2];
if (prevNonConflictingIndex != -1) currentProfit += dp[prevNonConflictingIndex]; //add profit to the previous found non-conflicting job
if (dp[i-1] < currentProfit) dp[i] = currentProfit; // if current profit is higher than previous index's profit till ith index
else dp[i] = dp[i-1]; // if excluding the current job leads to the maximum profit so far till i-1th index
}
return dp[n-1];
}
bool comparator(vector<int> a, vector<int> b) {
return a[1] == b[1] ? a[0] < b[0] : a[1] < b[1];
}
int main() {
vector<vector<int>> jobs{{0,6,60},{1,4,30},{3,5,10},{5,7,30},{5,9,50},{7,8,10}};
// sort jobs in increasing order of their finish times
sort(jobs.begin(), jobs.end(), comparator);
cout << "The maximum profit is " << findMaxProfit(jobs);
return 0;
}

The runtime complexity of the optimized approach is O(n*logn) and space complexity is O(n).

RELATED TAGS

algorithms
communitycreator

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring