Do you think IIT Guwahati certified course can help you in your career?
No
Introduction
The activity selection problem is an optimization problem that involves selecting a subset of mutually compatible activities from a given set of activities with specific start and finish times. The objective is to maximize the number of activities that can be completed while ensuring that no two activities overlap in time.
In this blog, we will discuss the activity selection problem and we will look at the different approaches that can be used to solve this problem.
Activity Selection Problem
Suppose we have a processor that can process only one activity simultaneously. And we have some tasks to be completed on that processor. Now, each task has a start time and end time, so the task will be assigned to the processor at the start time. The processor can start its execution if it is not engaged. Else it will not start the execution of the task and will wait till the current task is executed. Once it is over, it can start executing the next available task. So this problem is called activity selection, where we have to find the maximum no of non-overlapping activities that can be completed from a given set of activities.
There could be several approaches to solve this problem. But here we will discuss the solution using a greedy algorithm, which selects the activity with the earliest finish time in each step.
Greedy algorithms
Greedy algorithms make the best choice at each step to reach the overall optimal solution. So, while solving a problem with the greedy algorithm, we keep choosing the immediate best option.
For example, if we have to get a change for 80 rupees in the minimum number of coins, we have an infinite supply of coins of 50, 20, and 10. Then, the greedy algorithm will suggest picking up the coin with the highest denomination and taking as many as possible, but since taking two coins of 50 will become more than 80, we will pick one coin of 50, then move to the next highest denomination, i.e., 20 after taking 20, we only require one coin of 10. So we will pick one coin of 10 and get the minimum number of coins for change of 80 as 3.
We reached the optimal solution in the above example by choosing the best option at each stage. Thus any such problem can be solved using the greedy algorithm. Some examples of greedy algorithms are as follows-
Dijkstra's Shortest Path Algorithm.
Kruskal's Minimum Spanning Tree.
Prim's Minimum Spanning Tree.
Reverse delete algorithm for MST.
Activity selection using a greedy algorithm
First, we will see how we can solve this problem using a min-heap (priority queue) if the activities given are in random order. After that, we will see an optimized method to solve this question without using a priority queue.
One very important question is why we should always consider the first activity in the solution. The answer to this question lies in the problem statement itself. Since we have to find the maximum number of activities, the first activity will be the one that may or may not start late from some activities but will always finish first than any other activity. And choosing it will increase the no of activities completed to 1 in the least time.
Brute Force Approach
In this approach, we will store the array of activities in the min heap of pairs. After storing them in the min heap of pairs, we will process the top element of the priority queue. The first top element would be our first activity with the least finish time. After that, we will store the finish time of this activity in a variable named end, and we will start processing the remaining elements of the priority queue. We will consider an activity only when the start time of the activity is greater than the finish time of the previously considered activity, which is stored in the variable end. We will process the elements till the priority queue becomes empty.
Dry Run
So now let's dry run a sample test case to understand the problem better, consider the array of activities given below in the image.
Now will sort the array, and the steps given in the image below will be performed.
Algorithm for brute force approach
1. Insert all the activities in a min priority queue of pairs. We will make pairs like this {finish_time, start_time} for an activity and then insert it in the priority queue.
2. Take the top element of the priority queue and pop it. This is our first activity which is completed.
3. Store the end time of this activity in a variable end and start popping elements of the priority queue one by one.
4. Now, if the activity on the top of the priority queue has a start time greater than the end time of the previously selected activity, then cout this activity and update the end variable with the value of the end time of the currently selected activity.
5. Repeat this till the priority queue is not empty.
Implementation using C++
// Program for activity selection for any random order using a priority queue.
#include <bits/stdc++.h>
using namespace std;
// Structure for activity.
struct activity{
int start, end;
};
/*
Function to select a set of maximum activities that can be executed.
Given that only one activity can be executed at any instant.
*/
void solve(int n, vector<activity> actvty){
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
int x, y;
for (auto x: actvty){
// Since we sort by end time so we will insert
//activities in priority queue with a finish and start time
pq.push({x.end, x.start});
}
cout << "The activities are selected in following order: ";
// We will always select the activity with least finish time
x = 0;
auto current = pq.top();
auto start = current.second;
auto end = current.first;
pq.pop();
cout << "{" << start << "," << end << "} ";
// To select from the rest of the activities.
while (!pq.empty()){
current = pq.top();
pq.pop();
/*
An activity will be selected if it has a start time
greater than the end time of the previous activity.
*/
if (current.second >= end){
start = current.second;
end = current.first;
cout << "{" << start << "," << end << "} ";
}
}
}
// Driver function.
int main(){
int n = 6;
vector<activity> actvty = {{1, 2}, {4, 4}, {5, 10}, {9, 10}, {7, 8}, {2, 4}};
solve(n, actvty);
}
You can also try this code with Online C++ Compiler
Now we will see a more optimal approach, and here we will not use any extra array or Data Structure. Here we will sort the original array using a comparator function in the order of the activity's finish time. After that, we will process each activity just like the previous approach.
Dry Run
So now let's dry run a sample test case to understand the problem better, consider the array of activities given below in the image.
Now will sort the array, and the steps given in the image below will be performed.
Algorithm for optimal approach
1. Sort the activities in increasing order of their finish time.
2. Select the activity with the least finish time and execute it.
3. Now, we will select the next activity only when the start time of the current activity would be greater than the previously selected activity's finish time.
4. After selecting an activity, we will update the finish time by the current activity's finish time.
5. Repeat this till the array is completely traversed.
Implementation using C++
// Program for activity selection for any random order
#include <bits/stdc++.h>
using namespace std;
// Structure for activity.
struct activity{
int start, end;
};
// Comparator function for activities based on their end time.
bool compAct(activity a1, activity a2){
return (a1.end < a2.end);
}
/*
Function to select a set of maximum activities that can be executed.
Given that only one activity can be executed at any instant.
*/
void solve(int n, vector<activity> actvty){
int x, y;
sort(actvty.begin(), actvty.end(), compAct);
cout << "The activities are selected in following order." << endl;
// As the activities are sorted we will always select the first activity.
x = 0;
cout << "{" << actvty[x].start << "," << actvty[x].end << "} ";
// To select from the rest of the activities.
for (y = 1; y < n; y++){
/*
An activity will be selected if it has a start time
greater than the end time of the previous activity.
*/
if (actvty[y].start >= actvty[x].end){
cout << "{" << actvty[y].start << "," << actvty[y].end << "} ";
x = y;
}
}
}
// Driver function.
int main(){
int n = 6;
vector<activity> actvty = {{1, 2}, {4, 4}, {5, 10}, {9, 10}, {7, 8}, {2, 4}};
solve(n, actvty);
return 0;
}
You can also try this code with Online C++ Compiler
The time complexity of the above approach is- O(N*logN).
The space complexity of the above approach is- O(1).
Implementation Using python
from typing import List, Tuple
# Structure for activity
Activity = Tuple[int, int]
# Comparator function for activities based on their end time
def comp_act(a1: Activity, a2: Activity) -> bool:
return a1[1] < a2[1]
# Function to select a set of maximum activities that can be executed
# Given that only one activity can be executed at any instant
def solve(n: int, actvty: List[Activity]) -> None:
x, y = 0, 0
# Sort the activities by end time
actvty.sort(key=lambda x: x[1])
print("The activities are selected in the following order.")
# As the activities are sorted we will always select the first activity
print(f"{{{actvty[x][0]}, {actvty[x][1]}}}")
# To select from the rest of the activities
for y in range(1, n):
# An activity will be selected if it has a start time
# greater than the end time of the previous activity
if actvty[y][0] >= actvty[x][1]:
print(f"{{{actvty[y][0]}, {actvty[y][1]}}}")
x = y
# Driver function
if __name__ == "__main__":
n = 6
actvty = [(1, 2), (4, 4), (5, 10), (9, 10), (7, 8), (2, 4)]
solve(n, actvty)
You can also try this code with Online Python Compiler
Why will the greedy algorithm work for this problem?
A greedy algorithm works for the activity selection problem because of the following properties of the problem:
The problem has the 'greedy-choice property', which means that the locally optimal choice (the activity with the earliest finish time) leads to a globally optimal solution.
The problem has the 'optimal substructure' property, which means that an optimal solution to the problem can be constructed efficiently from optimal solutions to subproblems.
The greedy algorithm makes the locally optimal choice at each step by selecting the activity with the earliest finish time. This choice ensures that there is no overlap between the selected activities and that the maximum number of activities can be completed. Since the problem has the 'optimal substructure' property, a globally optimal solution can be constructed efficiently by making locally optimal choices at each step.
Frequently Asked Questions
Describe the limitations of the greedy algorithm.
The greedy algorithms can not consider future possibilities while making choices for solving a problem. It makes the best choice at each small step, which is sometimes not the optimal solution.
Assuming the activities are sorted, what is the time complexity of the greedy algorithm-based solution for the activity selection problem?
When the activities are sorted, the time complexity of the greedy algorithm-based solution for the activity selection problem will be O(N).
Is there a more optimal solution for the activity selection problem other than the one based on a greedy algorithm?
Even though the greedy algorithm has its limitations, the greedy algorithm-based solution for the activity selection problem is its optimal solution.
Is Dijkstra a greedy algorithm?
Yes, Dijkstra is a greedy algorithm. It is used in a directed graph to solve the single-source shortest path problem.
Which is faster Greedy methods or dynamic programming methods?
Generally, we consider the greedy methods to be faster than dynamic programming methods because, for dynamic programming methods, we need to use the DP table, which will need extra memory.
Conclusion
In this blog, we learned about the activity selection problem and greedy algorithms-
We started by understanding the problem statement and how a greedy algorithm can solve these problems. We went on to learn a little bit about greedy algorithms, what these are and how they work. After that, we discussed two different approaches to solve this problem. The first one was brute force and the second one was the optimal approach. In the end, we concluded with the FAQs.