What is Weighted Job Scheduling in Dynamic Programming?
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 timeint 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 foundreturn -1;}// A recursive function to find the maximum profit subset of non-overlapping jobs, which are sorted according to finish timeint findMaxProfit(vector<vector<int>> jobs, int index) {if (index < 0) return 0; // base caseif (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 jobint 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 indexint 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-1int excludeJob = findMaxProfit(jobs, index - 1);// return the maximum profit obtained by either including or excluding the current jobreturn 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 timessort(jobs.begin(), jobs.end(), comparator);// we call findMaxProfit function iteratively starting from the last jobcout << "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 timeint findPreviousNonConflictingJob(vector<vector<int>> jobs, int n) {// Binary search implementationint 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 indexdp[0] = jobs[0][2]; //initializing array with base case, i.e. 1st job's profitfor (int i = 1; i < n; i++){// find index of the last non-conflicting job with the current jobint prevNonConflictingIndex = findPreviousNonConflictingJob(jobs, i);int currentProfit = jobs[i][2];if (prevNonConflictingIndex != -1) currentProfit += dp[prevNonConflictingIndex]; //add profit to the previous found non-conflicting jobif (dp[i-1] < currentProfit) dp[i] = currentProfit; // if current profit is higher than previous index's profit till ith indexelse 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 timessort(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).
