Activity Selection Problem in Greedy Algorithm in C++

The activity selection problem is a classic optimization problem that involves selecting the maximum number of compatible activities from a given set. It is a well-known problem in computer science and has various applications, including scheduling tasks, resource allocation, and time management. In this article, we will explore the activity selection problem and discuss how it can be solved using the greedy algorithm in the C++ programming language.

Table of Contents

Explore Free Engineering Handwritten Notes!

Looking for comprehensive study materials on Python, Data Structures and Algorithms (DSA), Object-Oriented Programming (OOPs), Java, Software Testing, and more?

We earn a commission if you make a purchase, at no additional cost to you.

Activity Selection Problem

The problem statement goes like this: Given N activities with their start time and end time. The task is to find the solution set having a maximum number of non-conflicting activities that can be executed within the given time, assuming only a single activity can be performed at a given time.

They are more efficient than other techniques like Dynamic Programming. But it cannot be applied everywhere.

Understanding the Activity Selection Problem

The Activity Selection Problem is a classic optimization problem that involves selecting the maximum number of activities from a given set, given that they do not overlap. This problem is often encountered in scheduling and resource allocation scenarios, where efficient utilization of resources is paramount. By choosing the right set of activities, we can maximize productivity and ensure optimal resource allocation.

The standard Greedy Algorithms:

  1. Kruskal’s Minimum Spanning Tree (MST): It is used to generate a minimum spanning tree for a given graph. A Spanning tree is a subset of a connected graph G, where all the edges are connected.
  2.  Prim’s Minimum Spanning Tree: It finds a minimum cost spanning tree using the greedy approach.
  3. Dijkstra’s Algorithm: It allows us to find the shortest path between any two vertices of a graph. Two sets are maintained: a set of the vertices already included in the tree and the set of the vertices not yet included.
  4. Huffman Coding: It assigns variable-length bit codes to different characters. The Greedy Choice assigns the least bit length code to the most frequent character.

Input:

start[] = [10, 12, 20}]    

 end[] = [20, 25, 30]

Output: [0, 2]

Explanation: A maximum of two activities can be performed, i.e. Activity 0 and Activity 2[0-based indexing].

Sort the activities according to their finishing time so that we always consider the next activity as the minimum finishing time activity.

Firstly select the first activity from the sorted array and print it. Repeat the same for the remaining activities

Here are the programs which will work only on sorted arrays.

In C++

By implementing this algorithm in C++, you can efficiently solve the Activity Selection Problem and obtain the desired results. The code snippet below showcases a possible implementation:

#include <bits/stdc++.h>
using namespace std;

void printMaxActivities(int s[], int f[], int n)
{
	int i, j;

	cout <<"Following activities are selected "<< endl;

	i = 0;
	cout <<" "<< i;

	// Consider rest of the activities
	for (j = 1; j < n; j++)
	{
	
	if (s[j] >= f[i])
	{
		cout <<" " << j;
		i = j;
	}
	}
}

// driver program to test above function
int main()
{
	int s[] = {1, 3, 0, 5, 8, 5};
	int f[] = {2, 4, 6, 7, 9, 9};
	int n = sizeof(s)/sizeof(s[0]);
	printMaxActivities(s, f, n);
	return 0;
}

The output

Following activities are selected n0 1 3 4

Analyzing the Time Complexity of the Algorithm

The time complexity of the activity selection algorithm is dominated by the sorting step, which takes O(n log n) time, where n is the number of activities. The subsequent iteration over the sorted activities takes linear time, resulting in an overall time complexity of O(n log n). The space complexity of the algorithm is O(n) as we store the selected activities in a separate vector.

Real-life Applications of the Activity Selection Problem

The activity selection problem finds applications in various real-life scenarios. Some examples include:

  1. Conference scheduling: Selecting a set of talks that do not overlap in time.
  2. Project management: Determining the optimal sequence of tasks to maximize efficiency.
  3. Job scheduling: Assigning tasks to workers without conflicts.
  4. Classroom scheduling: Scheduling classes to avoid time clashes for students.

Advantages and Disadvantages of the Greedy Approach

The greedy approach to solving the activity selection problem offers several advantages, including simplicity and efficiency. It provides an optimal solution in a reasonable amount of time. However, it is important to note that the greedy algorithm may not always be applicable in every situation. There can be scenarios where the greedy approach fails to produce the optimal solution.

Tips for Optimizing the Algorithm

To optimize the activity selection algorithm, consider the following tips:

  1. Sort the activities based on finish time in ascending order before applying the greedy approach.
  2. Use efficient data structures and algorithms for sorting to minimize the time complexity.
  3. Avoid unnecessary iterations or comparisons when selecting activities.

Challenges and Considerations

While the greedy algorithm provides a straightforward solution to the activity selection problem, there are a few challenges and considerations to keep in mind:

  1. Conflicting activities: It is essential to properly define the compatibility criteria between activities to avoid conflicts.
  2. Input validation: Ensure that the input activities are valid and do not contain any overlapping intervals or invalid time values.
  3. Large input sizes: For a large number of activities, the time complexity of the algorithm becomes significant, and optimizations may be required.

Leave a Reply