Given a list of jobs where each job has a start and finish time, and also has profit associated with it, find maximum profit subset of non-overlapping jobs.

Job 1: (0, 6, 60)

Job 2: (1, 4, 30)

Job 3: (3, 5, 10)

Job 4: (5, 7, 30)

Job 5: (5, 9, 50)

Job 6: (7, 8, 10)

The maximum profit is 80 which is achieved by picking job 2 and Job 5.

This problem is standard variation of Activity Selection Problem. The greedy algorithm works fine for Activity Selection Problem since all jobs have equal weight. But greedy approach won’t work with weighted jobs since even single job may have more profit than all jobs combined.

### 1. Naive Recursive Solution

The idea is to sort the jobs in increasing order of their finish times and then use recursion to solve this problem. For each job, there are two possibilities –

- We include current job in result and recur only for non-conflicting jobs with the current job. Since the jobs are sorted according to their finish times, we can find the last non-conflicting job by performing a linear search or binary search on the sorted input.

- We exclude current job from result and recur for remaining items.

Finally, we return maximum profit we get by including or excluding current job. The recursive algorithm can be implemented as follows in C++:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
#include <iostream> #include <vector> #include <algorithm> using namespace std; // Data structure to store a Job struct Job { int start, finish, profit; }; // Function to find index of last job which doesn't conflict with the given job // It performs a linear search on the given vector of jobs int findLastNonConflictingJob(vector<Job> &jobs, int n) { // find index of the last job whose finish time is less than or equal to the // start time of the given job for (int i = n - 1; i >= 0; i--) { if (jobs[i].finish <= jobs[n].start) { return i; } } // return negative index if no non-conflicting job is found return -1; } // A recursive function to find maximum profit subset of non-overlapping // jobs which are sorted according to finish time int maxProfit(vector<Job> &jobs, int n) { // base case if (n < 0) return 0; // return if only one item is remaining if (n == 0) return jobs[0].profit; // find the index of last non-conflicting job with current job int index = findLastNonConflictingJob(jobs, n); // include the current job and recurse for non-conflicting jobs [0, index] int incl = jobs[n].profit + maxProfit(jobs, index); // exclude the current job and recur for remaining items [0, n-1] int excl = maxProfit(jobs, n-1); // return the maximum profit by including or excluding current job return max(incl, excl); } int main() { vector<Job> 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(), [](Job &x, Job &y) { return x.finish < y.finish; }); cout << "The maximum profit is " << maxProfit(jobs, jobs.size() - 1); return 0; } |

`Output:`

The maximum profit is 80

The time complexity of above solution is exponential and auxiliary space used by the program is O(n) for recursive call stack.

### 2. Dynamic Programming Solution

The above solution has an optimal substructure and also exhibits overlapping subproblems. So we can solve this problem in bottom-up manner using Dynamic Programming, in which we solve smaller sub-problems first, then solve larger sub-problems from them. The bottom-up approach can be implemented as follow:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
#include <iostream> #include <vector> #include <algorithm> using namespace std; // Data structure to store a Job struct Job { int start, finish, profit; }; // Function to find index of last job which doesn't conflict with the given job // It performs a linear search on the given vector of jobs int findLastNonConflictingJob(vector<Job> &jobs, int n) { // find index of the last job whose finish time is less than or equal to the // start time of the given job for (int i = n - 1; i >= 0; i--) { if (jobs[i].finish <= jobs[n].start) { return i; } } // return negative index if no non-conflicting job is found return -1; } // Function to find the maximum profit of non-overlapping jobs using DP int maxProfit(vector<Job> &jobs) { // sort jobs in increasing order of their finish times sort(jobs.begin(), jobs.end(), [](Job &x, Job &y) { return x.finish < y.finish; }); // get number of jobs int n = jobs.size(); // construct an lookup table where the i'th index stores the maximum profit // for first i jobs int maxProfit[n]; // maximum profit gained by including the first job maxProfit[0] = jobs[0].profit; // fill maxProfit[] table in bottom-up manner from the second index for (int i = 1; i < n; i++) { // find the index of last non-conflicting job with current job int index = findLastNonConflictingJob(jobs, i); // include the current job with its non-conflicting jobs int incl = jobs[i].profit; if (index != -1) incl += maxProfit[index]; // store the maximum profit by including or excluding current job maxProfit[i] = max(incl, maxProfit[i-1]); } // return maximum profit return maxProfit[n-1]; } int main() { vector<Job> 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(), [](Job &x, Job &y) { return x.finish < y.finish; }); cout << "The maximum profit is " << maxProfit(jobs); return 0; } |

`Output:`

The maximum profit is 80

The time complexity of above solution is O(n^{2}) where n is the number of items in the input. The auxiliary space used by the program is O(n).

### 3. Optimized Dynamic Programming Solution

We can further optimize above dynamic programming solution to run in `O(nlog(n))` time by using Binary Search algorithm to find the last non-conflicting job. The algorithm can be implemented as follows in C++:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
// Function to perform binary search on the given jobs which are // sorted by finish time. The function returns index of the last job // which doesn't conflict with the given job i.e. whose finish time // is less than or equal to the start time of the given job. int findLastNonConflictingJob(vector<Job> jobs, int n) { // search space int low = 0; int high = n; // iterate till search space is not exhausted while (low <= high) { int mid = (low + high) / 2; if (jobs[mid].finish <= jobs[n].start) { if (jobs[mid + 1].finish <= jobs[n].start) low = mid + 1; else return mid; } else { high = mid - 1; } } // return negative index if no non-conflicting job is found return -1; } |

### 4. Printing all jobs involved in the maximum profit

The idea is similar to above bottom-up approach using Dynamic Programming, but we maintain an extra array to store the index of jobs involved in the maximum profit. This is demonstrated below in C++:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 |
#include <iostream> #include <vector> #include <algorithm> using namespace std; // Data structure to store a Job struct Job { int start, finish, profit; }; // Function to perform binary search on the given jobs which are // sorted by finish time. The function returns index of the last job // which doesn't conflict with the given job i.e. whose finish time // is less than or equal to the start time of the given job. int findLastNonConflictingJob(vector<Job> jobs, int n) { // search space int low = 0; int high = n; // iterate till search space is not exhausted while (low <= high) { int mid = (low + high) / 2; if (jobs[mid].finish <= jobs[n].start) { if (jobs[mid + 1].finish <= jobs[n].start) low = mid + 1; else return mid; } else { high = mid - 1; } } // return negative index if no non-conflicting job is found return -1; } // Function to print the non-overlapping jobs involved in maximum profit // using Dynamic Programming void findMaxProfitJobs(vector<Job> &jobs) { // sort jobs in increasing order of their finish times sort(jobs.begin(), jobs.end(), [](Job &x, Job &y) { return x.finish < y.finish; }); // get number of jobs int n = jobs.size(); // maxProfit[i] stores the maximum profit possible for the first i jobs and // tasks[i] stores the index of jobs involved in the maximum profit int maxProfit[n]; vector<int> tasks[n]; // initialize maxProfit[0] and tasks[0] with the first job maxProfit[0] = jobs[0].profit; tasks[0].push_back(0); // fill tasks[] and maxProfit[] in bottom-up manner for (int i = 1; i < n; i++) { // find the index of last non-conflicting job with current job int index = findLastNonConflictingJob(jobs, i); // include the current job with its non-conflicting jobs int currentProfit = jobs[i].profit; if (index != -1) { currentProfit += maxProfit[index]; } // if including the current job leads to the maximum profit so far if (maxProfit[i-1] < currentProfit) { maxProfit[i] = currentProfit; if (index != -1) { tasks[i] = tasks[index]; } tasks[i].push_back(i); } // excluding the current job leads to the maximum profit so far else { tasks[i] = tasks[i-1]; maxProfit[i] = maxProfit[i-1]; } } // maxProfit[n-1] stores the maximum profit cout << "The maximum profit is " << maxProfit[n-1] << endl; // tasks[n-1] stores the index of jobs involved in the maximum profit cout << "The jobs involved in the maximum profit are: "; for (int i: tasks[n-1]) { cout << "(" << jobs[i].start << ", " << jobs[i].finish << ", " << jobs[i].profit << ") "; } } int main() { vector<Job> jobs { { 0, 6, 60 }, { 1, 4, 30 }, { 3, 5, 10 }, { 5, 7, 30 }, { 5, 9, 50 }, { 7, 8, 10 } }; findMaxProfitJobs(jobs); return 0; } |

`Output:`

The maximum profit is 80

The jobs involved in the maximum profit are: (1, 4, 30) (5, 9, 50)

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply