Given a set S of activities with start time and finish 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.

**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)

The activity selection problem is a problem concerning 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. A classic application of this problem is in scheduling a room for multiple competing events, each having its own time requirements (start and end time).

Lets assume there exist n activities with each of them being represented by a start time s_{i} and finish time f_{j}. Two activities i and j are said to be non-conflicting if s_{i} = f_{j} or s_{j} = f_{i}.

We can solve this problem by being greedy. Using greedy approach will always result in an optimal solution to this problem. We initially sorts the activities in increasing order of their finish times and create a set S to store the selected activities. We initialize the set with the first activity and then from the second activity onward, we include the activity in activities list if start time of the activity is greater or equal to the finish time of the last selected activity. We repeat this for each activity involved.

**C++ implementation –**

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 |
#include<bits/stdc++.h> using namespace std; struct Pair { // stores start time and finish time of the activities int start, finish; }; // Activity-Selection problem set<int> selectActivity(vector<Pair> vc) { // k keeps track of the index of the last selected activity int k = 0; // set to store the selected activities index set<int> out; // select 0 as first activity out.insert(0); // start iterating from the second element of // vector up to its last element for (int i = 1; i < vc.size(); i++) { // if start time of ith activity is is greater or equal // to the finish time of the last selected activity, it // can be included in activities list if (vc[i].start >= vc[k].finish) { out.insert(i); k = i; // update i as last selected activity } } return out; } // main function int main() { // vector of pairs with each pair storing start time // and finish time of the activities vector<Pair> v = { {1, 4}, {3, 5}, {0, 6}, {5, 7}, {3, 8}, {5, 9}, {6, 10}, {8, 11}, {8, 12}, {2, 13}, {12, 14} }; // Sort the activities according to their finishing time sort(v.begin(), v.end(), [](auto &lhs, auto &rhs) { return lhs.finish < rhs.finish; }); set<int> out = selectActivity(v); for (int i : out) cout << "(" << v[i].start << " " << v[i].finish << ")" << endl; return 0; } |

**Output: **

(1 4)

(5 7)

(8 11)

(12 14)

**Time complexity** of above solution is O(nlogn).

**Weighted Activity Selection Problem –**

Weighted Activity Selection Problem is the generalized version of the activity selection problem that involves selecting an optimal set of non-overlapping activities such that the total weight is maximized. Unlike the unweighted version, there is no greedy solution to the weighted activity selection problem. We will soon discuss a dynamic programming solution to this problem.

**References:**

https://en.wikipedia.org/wiki/Activity_selection_problem

http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Greedy/actSelectionGreedy.htm

**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