Activity Selection is a traditional issue in the field of computer science, commonly tackled through the application of greedy algorithms. In this scenario, we are presented with a collection of tasks scheduled for a specific timeframe. Each task is defined by a start time and an end time. The primary objective is to choose the highest possible quantity of tasks to execute, ensuring that none of them conflict with each other.
Let's explore an illustration to gain a clearer insight into this scenario. Assume you are dealing with five tasks: A, B, C, D, and E, with designated start and end times for each activity as listed below:
A: start = 1, end = 4
B: start = 3, end = 5
C: start = 0, end = 6
D: start = 5, end = 7
E: start = 8, end = 9
We observe that engaging in both activity A and D simultaneously results in a clash due to overlapping schedules. Therefore, the objective is to choose the highest possible quantity of activities that can run concurrently without conflicts. Resolving this issue involves the application of a greedy algorithm. The concept behind this algorithm is to consistently opt for the following activity that concludes earliest. By doing so, we guarantee the availability of the greatest amount of time for subsequent activities.
Here is a C++ implementation for solving the activity selection problem:
C++ Code
#include <bits/stdc++.h>
using namespace std;
struct Activity {
int start, end;
};
bool compare(Activity a, Activity b) {
return (a.end < b.end);
}
void printMaxActivities(Activity arr[], int n) {
sort(arr, arr + n, compare);
cout << "Following activities are selected: \n";
int i = 0;
cout << "(" << arr[i].start << ", " << arr[i].end << "), ";
for (int j = 1; j < n; j++) {
if (arr[j].start >= arr[i].end) {
cout << "(" << arr[j].start << ", " << arr[j].end << "), ";
i = j;
}
}
}
int main() {
Activity arr[] = {{5, 9}, {1, 2}, {3, 4}, {0, 6}, {5, 7}, {8, 9}};
int n = sizeof(arr) / sizeof(arr[0]);
printMaxActivities(arr, n);
return 0;
}
In the provided code snippet, we initially arrange the activities based on their finishing time to prioritize selecting the activity that completes earliest. Subsequently, a pair of pointers, namely i and j, are employed to monitor the ongoing activity and the subsequent one. Commencing with i = 0 and j = 1, we compare the start time of the following activity with the conclusion time of the ongoing activity. Should the start time of the subsequent activity be equal to or greater than the finishing time of the ongoing activity, both activities can be executed simultaneously without any overlap. In such cases, we advance j by one and assign i the value of j. This process persists until j reaches the conclusion of the array. The time complexity of this approach amounts to O(nlogn) since the activities necessitate prior sorting, which consumes O(nlogn) time. Moreover, the space complexity stands at O(1) since no additional space is utilized.
Output
Following activities are selected:
(1, 2), (3, 4), (5, 7), (8, 9),
Explanation:
The code above demonstrates the implementation of the activity selection dilemma using a greedy approach in C++. This particular problem is a well-known challenge in the field of computer science. In this scenario, a collection of activities is provided to be executed within a specified timeframe, with each activity having both a commencement time and a conclusion time. The objective is to choose the highest possible quantity of activities that can be executed without conflicting, ensuring that there are no overlapping activities.
The process kicks off by including the bits/stdc++.h header file, encompassing various standard C++ libraries. Subsequently, the Activity structure is established to hold the commencement and conclusion times of each activity. Following that, the compare function is introduced to arrange the activities in order of their culmination times. Sorting the activities in this manner allows us to prioritize selecting the activity that concludes earliest, maximizing the available time for subsequent activities.
The printMaxActivities method accepts an array containing activities and its size as parameters. It applies the greedy algorithm to address the activity selection problem. Initially, it arranges the activities in order of their conclusion time utilizing both the sort method and the compare function.
