Trusted answers to developer questions

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.

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.

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]`

: 0^{th} index gives you start time, with `jobs[i][0]`

representing start time of `i`

^{th} job.

`jobs[n][1]`

: 1^{st} index gives you end time, with `jobs[i][1]`

representing end time of `i`

^{th} job.

`jobs[n][2]`

: 2^{nd} index gives you the profit, with `jobs[i][2]`

representing profit you can earn by finishing `i`

^{th} job.

Return the maximum profit that you can obtain by executing `<= n`

jobs, ensuring there’s no overlap between any jobs.

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

10

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.

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 `0`

^{th} index, and if you decide to sort the array by `endTime`

, the problem will start from the `n-1`

^{th} 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-1`

^{th} index to `0`

^{th} 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.

#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-1`

^{th} index. So the worst case complexity for this scenario would be O(n*2^{n}).

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*2^{n}). Similarly, when `findPreviousNonConflictingJob()`

returns `i-1`

^{th} 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).

RELATED TAGS

algorithms

communitycreator

CONTRIBUTOR

Sankalp Kotewar

Grokking Modern System Design Interview for Engineers & Managers

Keep Exploring

Related Courses