Norway


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

 

This is called activity selection 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, }, {2, 13}, {, 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 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
     = 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 Star  - rating on - Activity Selection Problem using Dynamic Programming2 Stars  - rating on - Activity Selection Problem using Dynamic Programming3 Stars  - rating on - Activity Selection Problem using Dynamic Programming4 Stars  - rating on - Activity Selection Problem using Dynamic Programming5 Stars  - rating on - Activity Selection Problem using Dynamic Programming (3 votes, average: 5.00 out of 5)

- loading - Activity Selection Problem using Dynamic ProgrammingLoading…

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 🙂
 



Source link

LEAVE A REPLY

Please enter your comment!
Please enter your name here