  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, 6}
L: {1, 4}
L: {2, 13}
L: {3, 5}
L: {3, 8}
L: {1, 4} {5, 7}
L: {1, 4} {5, 9}
L: {1, 4} {6, 10}
L: {1, 4} {5, 7} {8, 11}
L: {1, 4} {5, 7} {8, 12}
L: {1, 4} {5, 7} {8, 11} {12, 14}

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

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

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).     (3 votes, average: 5.00 out of 5) Loading…