Activity Scheduling Problem

Explore the activity scheduling problem and understand how to select the maximum number of compatible activities using greedy algorithms. Learn to optimize solutions by sorting activities by finish time, reducing complexity, and applying an iterative approach suitable for coding interviews.

We'll cover the following...

Problem Statement
Brute Force Solution
Greedy Iterative Solution
- Pseudocode

Problem Statement

Say you are given $n$ activities with their start and finish times. Select 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.

Mathematically, Let $S$ $=$ ${1, 2, . . . , n}$ be the set of activities that compete for a resource. Each activity $i$ has its starting time $s_i$ and finish time $f_i$ with $s_i$ $≤$ $f_i$ , namely, if selected, i takes place during time [ $s_i$ , $f_i$ ). No two activities can share the resource at any time point. We say that activities $i$ and $j$ are compatible if their time periods are disjoint.

The activity-selection problem is the problem of selecting the largest set of mutually compatible activities.

C++

// where
// n = Total number of activities 
// start[] = start time of all activities 
// finish[] = finish time of all activities 
void maxActivities(int start[], int finish[], int n) {
  int index, j;
  std::vector < int > finalActivities;
  std::vector < int > tempActivities;
  cout << "Following activities are selected: 0 ";
  // Array that will help us find all combinations possible of the activities
  int combinations[n];
  for (int i = 0; i < n; i++)
    combinations[i] = i;
  // find value for all combinations
  do {
    index = 0; //starting activity always 0
    for (j = 1; j < n; j++) {
      if (start[combinations[j]] >= finish[combinations[index]]) {
        tempActivities.push_back(combinations[j]);
        index = j;
      }
    }
    if (tempActivities.size() > finalActivities.size())
      finalActivities = tempActivities;
    tempActivities.erase(tempActivities.begin(), tempActivities.end());
  } while (std::next_permutation(combinations, combinations + n));
  //printing the sequence with max tasks
  for (int i = 0; i < finalActivities.size(); i++)
    cout << finalActivities[i] << " ";
}
int main() {
  int start[] = {0, 3, 3, 2, 4, 3, 8, 10};
  int finish[] = {3, 4, 5, 7, 8, 11, 12, 13 };
  int n = sizeof(start) / sizeof(start[0]);
  maxActivities(start, finish, n);
  return 0;
}

As you can see from the code above, such an approach is very naive. Plus the time complexity is $O(2^n)$ since we try all possible combinations of the activities.

However, a slight greedy tweak can really help us reduce the time complexity of our solution

By looking at the figure above, we can deduce that if we sort the activities on the final time of the activities, we can intuitively assign the resources that are free to the next task. Let’s have a look at the pseudocode for solving this algorithm:

Greedy Iterative Solution

Pseudocode

GreedyIterativeActivitySelector(A, s, f): 
    Sort A by finish times stored in f
    S = {A[1]} 
    k = 1
    n = A.length
    
    for i = 2 to n:
       if s[i] ≥ f[k]: 
           S = S U {A[i]}
           k = i
    
    return

This algorithm is called Greedy-Iterative-Activity-Selector.

In this pseudocode, $A$ is an array containing the activities, $s$ is an array containing the start times of the activities in $A$ , and $f$ is an array containing the finish times of the activities in $A$ . Note, these arrays are indexed starting from 1 up to the length of the corresponding array.

Firstly, sort the array of activities in increasing order of finish times by using the finish times stored in the array $f$ . This operation can be done in $O(n log_2 n)$ time, using the fastest available sorting algorithms. For revision of sorting algorithms see this chapter. Next, create a set $S$ to store the selected activities, and initialize it with the activity $A[1]$ . Start iterating from the second element of that array $A$ up to its last element and, if the start time $s[i]$ of the $i$ th activity ( $A[i]$ ) is greater or equal to the finish time $f[k]$ of the last selected activity ( $A[k]$ ), then $A[i]$ is compatible with the selected activities in the set $S$ , and thus it can be added to $S$ .

C++

bool sortbysec(const pair<int,int> &a, const pair<int,int> &b) { 
  return a.second < b.second; 
}
 
void maxActivities(int start[], int finish[], int n) {
  vector< pair <int,int> > zipped; //zipping start and finish arrays together
  for(int i = 0; i < n; i++)
    zipped.push_back(make_pair(start[i], finish[i]));
  
  sort(zipped.begin(), zipped.end(), sortbysec); 
  int index, j;
  cout << "Following activities are selected: ";
  // select first activity
  index = 0;
  cout << index << " ";
  for (j = 1; j < n; j++) {
    if (zipped[j].first >= zipped[index].second) {
      cout << j << " ";
      index = j;
    }
  }
}
int main() {
  int start[] = {0, 3, 3, 2, 4, 3, 8, 10};
  int finish[] = {3, 4, 5, 7, 8, 11, 12, 13};
  int n = sizeof(start) / sizeof(start[0]);
  maxActivities(start, finish, n);
  return 0;
}

1.Introduction

2.Algorithmic Paradigms

3.Introduction to Complexity Measures

4.Sorting & Searching

5.Graph Algorithms

6.Greedy Algorithms

7.Dynamic Programming

8.Divide and Conquer

9.Appendix: Auxiliary Source Code

10.Conclusion

Activity Scheduling Problem

Problem Statement

Brute Force Solution

Greedy Iterative Solution

Pseudocode