Given a set of activities and the starting & finishing time of each activity, find the maximum number of activities that can be performed by a single person assuming that a person can only work on a single activity at a time.

This problem is called activity selection problem which concerns the selection of non-conflicting activities to perform within a given time frame, given a set of activities each marked by a start and finish time. For example,

**Input:**

{1, 4}, {3, 5}, {0, 6}, {5, 7}, {3, 8}, {5, 9},

{6, 10}, {8, 11}, {8, 12}, {2, 13}, {12, 14}

**Output:** {1, 4}, {5, 7}, {8, 11}, {12, 14}

In the previous post, we have discussed a greedy approach for activity selection problem. In this post, we will discuss a dynamic programming solution for activity selection problem which is nothing but a variation of Longest Increasing Subsequence problem.

The idea is to first sort given activities in increasing order of their start time. Let `jobs[0..n-1]` be the sorted array of activities. We can define an array `L[]` such that `L[i]` itself is an array that stores maximum non-conflicting jobs ending at `i'th` job. Therefore, `L[i]` can be recursively written as –

L[i] = jobs[i] + { max(L[j]) where j < i and jobs[j].end < jobs[i].start }

= jobs[i], if there is no such j

For example, consider below sorted activities:

{0, 6} {1, 4} {2, 13} {3, 5} {3, 8} {5, 7} {5, 9} {6, 10} {8, 11} {8, 12} {12, 14}

Then `L[]` would be:

L[0]: {0, 6}

L[1]: {1, 4}

L[2]: {2, 13}

L[3]: {3, 5}

L[4]: {3, 8}

L[5]: {1, 4} {5, 7}

L[6]: {1, 4} {5, 9}

L[7]: {1, 4} {6, 10}

L[8]: {1, 4} {5, 7} {8, 11}

L[9]: {1, 4} {5, 7} {8, 12}

L[10]: {1, 4} {5, 7} {8, 11} {12, 14}

##### 1. Count the maximum number of non-conflicting jobs

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 |
#include <iostream> #include <algorithm> #include <vector> using namespace std; // Data structure to store the start and finish time of the jobs struct Pair { int start; int finish; }; // Returns the maximum count of non-conflicting jobs that can be performed // by a single person int findNonConflictingJobsLength(vector<Pair> &jobs) { // sort the jobs according to increasing order of their start time sort(jobs.begin(), jobs.end(), [](Pair &x, Pair &y) { return x.start < y.start; }); // L[i] stores the maximum count of non-conflicting jobs ending at i'th job vector<int> L(jobs.size()); for (int i = 0; i < jobs.size(); i++) { // consider each j less than i for (int j = 0; j < i; j++) { // L[i] = max(L[j]) where jobs[j].finish is less than jobs[i].start if (jobs[j].finish < jobs[i].start && L[i] < L[j]) { L[i] = L[j]; } } // increment L[i] since it ends at the i'th job L[i]++; } // return maximum job length in the vector return *max_element(L.begin(), L.end()); } int main() { // Each pair stores the start and the finish time of a job vector<Pair> jobs = { {1, 4}, {3, 5}, {0, 6}, {5, 7}, {3, 8}, {5, 9}, {6, 10}, {8, 11}, {8, 12}, {2, 13}, {12, 14} }; cout << "The maximum number of non-conflicting jobs are " << findNonConflictingJobsLength(jobs); return 0; } |

`Output:`

The maximum number of non-conflicting jobs are 4

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

`O(n)`.

##### 2. Print the maximum number of non-conflicting jobs

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 |
#include <iostream> #include <algorithm> #include <vector> using namespace std; // Data structure to store the start and finish time of the jobs struct Pair { int start; int finish; }; // Find the maximum number of non-conflicting jobs that can be performed // by a single person void findNonConflictingJobs(vector<Pair> &jobs) { // sort the jobs according to increasing order of their start time sort(jobs.begin(), jobs.end(), [](Pair &x, Pair &y) { return x.start < y.start; }); // L[i] stores the maximum non-conflicting jobs that ends at i'th job vector<vector<Pair>> L(jobs.size()); for (int i = 0; i < jobs.size(); i++) { // consider each j less than i for (int j = 0; j < i; j++) { // L[i] = max(L[j]) where jobs[j].finish is less than jobs[i].start if (jobs[j].finish < jobs[i].start && L[i].size() < L[j].size()) { L[i] = L[j]; } } // L[i] ends at i'th job L[i].push_back(jobs[i]); } // find the vector having maximum size vector<Pair> max; for (auto &pair: L) { if (max.size() < pair.size()) { max = pair; } } // print maximum non-conflicting jobs for (Pair &pair: max) { cout << "{" << pair.start << ", " << pair.finish << "} "; } } int main() { // Each pair stores the start and the finish time of a job vector<Pair> jobs = { {1, 4}, {3, 5}, {0, 6}, {5, 7}, {3, 8}, {5, 9}, {6, 10}, {8, 11}, {8, 12}, {2, 13}, {12, 14} }; findNonConflictingJobs(jobs); return 0; } |

`Output:`

{1, 4} {5, 7} {8, 11} {12, 14}

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

`O(n`.

^{2})

**Thanks for reading.**

Please use our online compiler to post code in comments. To contribute, get in touch with us.

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

## Leave a Reply