Activity Selection presents a challenge in combinatorial optimization, where the objective is to maximize the number of activities that can be completed by one individual within a given set of activities and their respective start and end times. In this scenario, it's essential to remember that each person can handle only one activity at any given time. The solution to the activity selection problem often involves leveraging greedy algorithms, which excel at making optimal decisions in the present moment without reconsidering past choices. The fundamental principle guiding a greedy algorithm's approach to the activity selection problem is to consistently opt for the activity with the earliest finishing time, thereby enabling the execution of the highest possible number of activities.
To apply a greedy strategy to address the activity selection problem, the initial step involves arranging the activities in ascending order based on their end times. Once the sorting is completed, the process begins by selecting the first activity and adding it to the largest possible collection of activities. Subsequently, the algorithm proceeds to select the subsequent activity that commences after the conclusion of the ongoing activity and incorporates it into the group. This sequence repeats iteratively until additional activities cannot be appended to the set. The procedure for executing this algorithm is uncomplicated and direct, outlined as below:
Sort the activities in non-descending order of their finish times.
- Initialize the current activity to be the first activity in the sorted array.
- For each subsequent activity, if its start time is greater than or equal to the finish time of the current activity, include it in the subset and update the current activity to be this activity.
- Repeat step 3 until all activities have been considered.
- The time complexity of the greedy algorithm for the activity selection problem is O(n log n), where n is the number of activities. This is because sorting the activities takes O(n log n) time and the rest of the algorithm takes O(n) time.
The greedy algorithm for the activity selection problem has several important properties:
- Optimal Substructure: If an optimal solution to the activity selection problem contains a particular activity, then it must also contain all the activities that precede it in the sorted array.
- Greedy Choice Property: A greedy algorithm for the activity selection problem makes the locally optimal choice at each step, that is, it selects the activity that finishes earliest. This choice leads to a globally optimal solution.
- The proof of the correctness of the greedy algorithm for the activity selection problem can be established using these two properties. In essence, it can be shown that the greedy choice of selecting the activity that finishes earliest at each step leads to an optimal solution to the problem.
C++ Code
#include<iostream>
#include<algorithm>
using namespace std;
// Structure to represent an activity
struct Activity {
int start, finish;
};
// Comparison function to sort the activities based on their finish time
bool activityCompare(Activity s1, Activity s2) {
return (s1.finish < s2.finish);
}
// Function to print the maximum number of activities that can be performed
void printMaxActivities(Activity arr[], int n) {
sort(arr, arr+n, activityCompare);
int i = 0;
cout << "The following activities are selected: " << endl;
// Select the first activity
cout << "(" << arr[i].start << ", " << arr[i].finish << ") ";
// Iterate through the rest of the activities
for (int j = 1; j < n; j++) {
// If this activity has a start time greater than or equal to
// the finish time of the previous activity, select it
if (arr[j].start >= arr[i].finish) {
cout << "(" << arr[j].start << ", " << arr[j].finish << ") ";
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;
}
Output
The following activities are selected:
(1, 2) (3, 4) (5, 7) (8, 9)
Explanation:
In summary, the activity selection dilemma serves as a prime illustration of a situation that can be resolved through the application of greedy algorithms. The greedy approach to this particular issue is straightforward to execute, boasts a manageable time complexity, and ensures the derivation of an optimal outcome. By familiarizing ourselves with the activity selection problem and its resolution, we can develop a more profound admiration for the efficiency and sophistication of greedy algorithms, and the valuable perspective they offer in addressing optimization challenges.
