Activity Selection Problem For A Sorted Finished Array

Let's start by understanding the problem statement for this task.

In an activity selection problem, you are given a set of activities with their start and the finish time in different arrays and your work is to select the maximum number of activities provided that you can select only one activity at a time.

Hint:

Selecting an activity one at a time means that you cannot select an activity unless and until you have completed the previous activity gets finished, and also the start time of the next activity must be greater than the finish time of the previous time for the selection of the activity.

Quick Think:

For creating an algorithm for an activity selection problem, the programmer has to keep the following things in mind:-

1. Keep comparing the finish time array with the start time array of each activity array, if the finish time of the previous activity is less than the start time of the next activity, select it.
2. A maximum number of activities must be selected keeping the condition in mind.

Algorithm:

For creating the activity selection array, the algorithm followed should be as follows:-

Step1: Declare a function with arguments as the start time array, finish time array, and the size of the array.

Step2: Now define a variable that will be our counter variable for the finish time array and declare it as 0.

Step3: Define a for loop to traverse through the start time array and keep comparing the finish time and the start time arrays simultaneously with each other, if the data element of the finish time array is less than that of the start time array then select that particular activity and print it.

Step4: After traversing through the complete array, and the loop and print the complete desired array.

Implementation Of the Above Algorithm:

Implementation of the above-given algorithm is as follows:-

#include <bits/stdc++.h>
using namespace std;
// Driver function to compare the two arrays.
void activity_selection(int start[], int finish[], int n)
{
	int i, j;
	cout << "The following is the required set of activities." << endl;
	i = 0;
	cout << i << " ";
	for (j = 1; j < n; j++)
	{
		if (start[j] >= finish[i])
		{
			cout << j << " ";
			i = j;
		}
	}
}

// Driver program to test above function.
int main()
{
	int start[] = { 1, 3, 0, 5, 8, 5 };

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

	int n = sizeof(start) / sizeof(start[0]);
	activity_selection(start, finish, n);
	return 0;
}

The time complexity of the above algorithm is: O(n).

The output of the above algorithm is: 0 1 3 4.

Explanation Of Above Algorithm:

• In the above code, let us consider two arrays of start and finish, as shown in the figure above.

• Since, as mentioned above, the first activity is always selected, we will select the first activity and print its index as 0 as shown in the diagram above.

• Now we will see that the finish time of the first activity is less than the start time of the second activity, hence the second activity is selected, and its index is printed as shown in the above diagram.

• Similarly, the finish time of the second activity is less than the start time of the fourth activity, and its index is printed as shown in the above diagram.

• And in this way, the array is traversed, and all activities are selected as shown in the above diagram.