# Activity Selection problem

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

### Problem Statement

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. If selected activity takes place during time [s_i, f_i). No two activities can share the resource at any time point. We say the activities i and j are compatible if their time periods are disjoint.

### 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_0}
j = 1
for i=2 to n do
if s_i >= f_j then
S = S U {A_i}
j = i;

### Code

//
//  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.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);

for (int i=0; i<selectedActivities.size(); i++) {
cout<<selectedActivities[i]<<" ";
}
return 0;
}



Here’s a working example:

https://ideone.com/75VzHD