Activity Selection problem

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 fi. No two activities can share the resource at any time point. So, if a selected activity i takes place during time [si, fi), we cannot add any other activity j such that sj >= si and sj < fi. 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 = {A1}
j = 1

for i = 2 to n do
  if si >= fj then
     S = S U {Ai}
     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