Activity Selection Problem using Dynamic Programming

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

 

Download   Run Code

Output:

The maximum number of non-conflicting jobs are 4

 
The time complexity of above solution is O(n2) 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

 

Download   Run Code

Output:

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

 
The time complexity of above solution is O(n2) where n is the number of given activities. The auxiliary space used by the program is O(n2).

 
1 Star2 Stars3 Stars4 Stars5 Stars (2 votes, average: 5.00 out of 5)

Loading...

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

avatar
  Subscribe  
Notify of