Activity selection problem is the problem of selecting the largest set of mutually exclusive activities.

**Problem**

Let S = {1, 2, …n} be the set of activities that compete for a resource. Each activity has its own starting time s_{i} and finish time f_{i}. No two activities can share the resource at any time point. So, if a selected **activity i** takes place during time [s_{i}, f_{i}), we cannot add any other **activity j** such that s_{j }>= s_{i} and s_{j} < f_{i}. We say the activities ** i** and

**are compatible if their time periods are disjoint.**

*j*###### Greedy activity selection algorithm

In this algorithm, the activities are first sorted according to their finish time f, from the earliest to the latest where a tie can be broken arbitrarily. Then activities are greedily selected by going down the list and by picking whatever activity ie. compatible with current selection.

###### Algorithm running time

Time complexity = Sorting + Selecting = **O(n*logn + n)**

That is **O(nlogn)**.

###### Pseudocode

start[] = {1, 3, 0, 5, 8, 5}

finish[] = {2, 4, 6, 7, 9, 9}

The greedy choice is to always select the next activity whose finish time is least among the remaining activities and start is more than or equal to the finish time of previously selected activity.

S = {A_{1}} j = 1 for i=2 to n do if s_{i}>= f_{j}then S = S U {A_{i}} j = i;

You could read about Custom comparators here.

**Code Implementation**

```
//
// main.cpp
// Activity Selection
//
// Created by Himanshu on 16/08/21.
//
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef struct node Node;
struct node {
int s, f;
int pos;
};
//Custom comparator
bool cmp (const Node &a, const Node &b){
return a.f < b.f;
}
vector<int> solve(vector<int> s, vector<int> f) {
vector<int> ans;
int N = (int)s.size(), j = 0;
Node p[N];
for (int i=0; i<N; i++) {
p[i].s = s[i];
p[i].f = f[i];
p[i].pos = i;
}
sort(p, p+N, &cmp);
ans.push_back(p[0].pos);
for (int i=1; i<N; i++) {
if (p[i].s >= p[j].f) {
ans.push_back(p[i].pos);
j = i;
}
}
return ans;
}
int main() {
vector<int> start = {1, 3, 0, 5, 8, 5};
vector<int> finish = {2, 4, 6, 7, 9, 9};
vector<int> selectedActivities = solve(start, finish);
cout<<"Selected activities: \n";
for (int i=0; i<selectedActivities.size(); i++) {
cout<<selectedActivities[i]<<" ";
}
return 0;
}
```

**Output**

Selected activities: 0 1 3 4

Here’s a working example: Ideone

## One thought on “Activity Selection problem”