Activity Selection Problem in Greedy Algorithm in C/C++/Java/Python
The Activity Selection problem is an approach to selecting non-conflicting tasks based on start and end time which can be solved in O(N logN) time using a simple greedy approach.
Greedy algorithms are used for optimization problems.
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.
The standard Greedy Algorithms:
- 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 to a connected graph G, where all the edges are connected.
- Prim’s Minimum Spanning Tree: It finds a minimum cost spanning tree using the greedy approach.
- 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.
- 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++
#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
In Java
import java.util.*;
import java.lang.*;
import java.io.*;
class ActivitySelection
{
public static void printMaxActivities(int s[], int f[], int n)
{
int i, j;
System.out.print("Following activities are selected : n");
// The first activity always gets selected
i = 0;
System.out.print(i+" ");
// Consider rest of the activities
for (j = 1; j < n; j++)
{
if (s[j] >= f[i])
{
System.out.print(j+" ");
i = j;
}
}
}
public static void main(String[] args)
{
int s[] = {1, 3, 0, 5, 8, 5};
int f[] = {2, 4, 6, 7, 9, 9};
int n = s.length;
printMaxActivities(s, f, n);
}
}
The output
Following activities are selected n0 1 3 4
In C
#include<stdio.h>
void printMaxActivities(int s[], int f[], int n)
{
int i, j;
printf ("Following activities are selected n");
// The first activity always gets selected
i = 0;
printf("%d ", i);
// Consider rest of the activities
for (j = 1; j < n; j++)
{
if (s[j] >= f[i])
{
printf ("%d ", j);
i = j;
}
}
}
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
In Python
def printMaxActivities(s , f ):
n = len(f)
print ("The following activities are selected")
# The first activity is always selected
i = 0
print (i,end=' ')
# Consider rest of the activities
for j in range(n):
if s[j] >= f[i]:
print (j,end=' ')
i = j
# Driver program to test above function
s = [1 , 3 , 0 , 5 , 8 , 5]
f = [2 , 4 , 6 , 7 , 9 , 9]
printMaxActivities(s , f)
The output
Following activities are selected n0 1 3 4
What to do when the arrays are not sorted?
We have to create a structure/class for activities and sort all activities by finish time. Then follow the same algorithm.
In C++
#include <bits/stdc++.h>
using namespace std;
// A job has a start time, finish time and profit.
struct Activitiy
{
int start, finish;
};
bool activityCompare(Activitiy s1, Activitiy s2)
{
return (s1.finish < s2.finish);
}
void printMaxActivities(Activitiy arr[], int n)
{
// Sort jobs according to finish time
sort(arr, arr+n, activityCompare);
cout << "Following activities are selected n";
// The first activity always gets selected
int i = 0;
cout << "(" << arr[i].start << ", " << arr[i].finish << "), ";
for (int j = 1; j < n; j++)
{
if (arr[j].start >= arr[i].finish)
{
cout << "(" << arr[j].start << ", "
<< arr[j].finish << "), ";
i = j;
}
}
}
// Driver program
int main()
{
Activitiy 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;
}
The output:
Following activities are selected
(1, 2), (3, 4), (5, 7), (8, 9),
In Java
import java.io.*;
import java.util.*;
class Activity
{
int start, finish;
// Constructor
public Activity(int start, int finish)
{
this.start = start;
this.finish = finish;
}
}
class Compare
{
static void compare(Activity arr[], int n)
{
Arrays.sort(arr, new Comparator<Activity>()
{
@Override
public int compare(Activity s1, Activity s2)
{
return s1.finish - s2.finish;
}
});
}
}
class GFG {
static void printMaxActivities(Activity arr[], int n)
{
Compare obj = new Compare();
obj.compare(arr, n);
System.out.println(
"Following activities are selected :");
int i = 0;
System.out.print("(" + arr[i].start + ", "
+ arr[i].finish + "), ");
// Consider rest of the activities
for (int j = 1; j < n; j++)
{
if (arr[j].start >= arr[i].finish)
{
System.out.print("(" + arr[j].start + ", "
+ arr[j].finish + "), ");
i = j;
}
}
}
// Driver code
public static void main(String[] args)
{
int n = 6;
Activity arr[] = new Activity[n];
arr[0] = new Activity(5, 9);
arr[1] = new Activity(1, 2);
arr[2] = new Activity(3, 4);
arr[3] = new Activity(0, 6);
arr[4] = new Activity(5, 7);
arr[5] = new Activity(8, 9);
printMaxActivities(arr, n);
}
}
The output
Following activities are selected
(1, 2), (3, 4), (5, 7), (8, 9),
In Python
def MaxActivities(arr, n):
selected = []
Activity.sort(key = lambda x : x[1])
# The first activity always gets selected
i = 0
selected.append(arr[i])
for j in range(1, n):
if arr[j][0] >= arr[i][1]:
selected.append(arr[j])
i = j
return selected
Activity = [[5, 9], [1, 2], [3, 4], [0, 6],[5, 7], [8, 9]]
n = len(Activity)
selected = MaxActivities(Activity, n)
print("Following activities are selected :")
print(selected)
The output
Following activities are selected (1, 2), (3, 4), (5, 7), (8, 9),
Time Complexity
When activities are sorted by their finish time: O(N)
When activities are not sorted by their finish time, the time complexity is O(N log N) due to the complexity of sorting