We are given `N`

activities with their start time and finish time. Our task is to find the maximum number of non-conflicting activities that can be performed within a given time assuming that only a single activity can be performed at a time.

## Scope

In this article we are looking upon Activity selection problem.

In this article we will learn constrins of activity selection problem.

In this article we will different approch of solving activity selection problem.

## Takeaways

Time and Space Complexity for the Greedy approach when the given set of activities are not sorted is `O(nlogn)`

and `O(1)`

## Example of Activity Selection Problem

```
Input:
N = 3
arr[] = {{10, 20}, {12, 25}, {20, 30}}
Output:
(10, 20) (20, 30)
Input:
N = 4
arr[] = {{3, 4}, {2, 5}, {1, 3}, {5, 9}, {0, 7}, {11, 12}, {8, 10}}
Output:
(1, 3) (3, 4) (5, 9) (11, 12)
```

**Example Explanation**

Suppose we are given the following 7 activities:

```
arr[] = {{3, 4}, {2, 5}, {1, 3}, {5, 9}, {0, 7}, {11, 12}, {8, 10}}
```

Let us create 2 different arrays for start and finish time and sort them by finish time for better understanding:

```
start[] = {1, 3, 2, 0, 5, 8, 11}
finish[] = {3, 4, 5, 7, 9, 10, 12}
```

Since these activities are already sorted by their finish time, firstly the activity0 gets selected. As the start time of activity1 is equal to the finish time of activity0, it will also get selected. activity2 and activity3 are having smaller start times as compared to the finish time of activity1, so both these activities will get rejected.

Similarly activity4 and activity6 are also selected, whereas activity5 will be rejected. Therefore at the end of an iteration, activities at index 0, 1, 4, and 6 will be performed, while others get rejected.

## Constraints of Activity Selection Problem

$1 ≤ N ≤ 2*10^{5}$

$1 ≤ arr[i] ≤ 10^{9}$

### Approach 1: Greedy algorithm

**Intuition:**

This method uses the`greedy approach`

and as the name suggests greedy means that at every step we have to make a choice that looks best at the moment and can provide us with an optimal solution for that problem. Since we have to maximize the number of performed activities, so we will be choosing the activity that will finish first as that will leave us with the maximum time to process the remaining activities. This greedy intuition enables us to make choices and provide us with an optimal solution and also helps us to get started with the solution. Therefore, our first task is to sort the activities based on their finish time.*If we try to solve this problem by sorting the activities based on start time then there might be a case where the activity with the least start time takes maximum duration to complete thus preventing us from maximizing the number of activities.***Algorithm:**- Sort all activities based on their finish time.
- Choosing the first activity from the sorted list.
- Select the next activity from the sorted list only if its
`start`

time is greater than or equal to the`finish`

time of the previously selected activity. - Repeat
`Step 3`

for all the remaining activities in the sorted list.

**Implementation**

**C++ Program to solve Activity Selection Problem using Greedy Algorithm**:

```
#include <bits/stdc++.h>
using namespace std;
```*// An activity has a start, and finish time.*
struct Activity
{
int start, finish;
};
*// Sorting activities by finish time*
bool compare(Activitiy a1, Activitiy a2)
{
return (a1.finish < a2.finish);
}
void activitySelection(Activity arr[], int n)
{
*// calling sort function*
sort(arr, arr+n, compare);
cout << "Selected Actvities are : ";
*// First activity will be always selected*
int i = 0;
cout << "(" << arr[i].start << ", " << arr[i].finish << ") ";
*// Traversing for remaining activities*
for (int j = 1; j < n; j++)
{
*// If start time of current activity >= finish time of previous activity*
if (arr[j].start >= arr[i].finish)
{
cout << "(" << arr[j].start << ", " << arr[j].finish << ") ";
i = j;
}
}
}
int main()
{
Activity arr[] = {{3, 4}, {2, 5}, {1, 3}, {5, 9}, {0, 7}, {11, 12}, {8, 10}};
int n = sizeof(arr)/sizeof(arr[0]);
*// calling selection function*
activitySelection(arr, n);
return 0;
}

**Output:**

```
Selected Actvities are : (1, 3) (3, 4) (5, 9) (11, 12)
```

**Java Program to solve Activity Selection Problem using Greedy Algorithm**:

```
import java.io.*;
import java.util.*;
```*// An activity has a start time, and finish time.*
class Activity
{
int start, finish;
*// Activity Constructor*
public Activity(int start, int finish)
{
this.start = start;
this.finish = finish;
}
}
class Compare
{
*// Sorting activities by finish time*
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 Main
{
static void activitySelection(Activity arr[], int n)
{
*// calling sorting function*
Compare obj = new Compare();
obj.compare(arr, n);
System.out.print("Selected Activities are : ");
*// The first activity will be always selected*
int i = 0;
System.out.print("(" + arr[i].start + ", "
+ arr[i].finish + ") ");
*// Traversing remaining activities*
for (int j = 1; j < n; j++)
{
*// If current activity has start time >= finish time of previously selected activity*
if (arr[j].start >= arr[i].finish)
{
System.out.print("(" + arr[j].start + ", "
+ arr[j].finish + ") ");
i = j;
}
}
}
public static void main(String[] args)
{
int n = 7;
Activity arr[] = new Activity[n];
arr[0] = new Activity(3, 4);
arr[1] = new Activity(2, 5);
arr[2] = new Activity(1, 3);
arr[3] = new Activity(5, 9);
arr[4] = new Activity(0, 7);
arr[5] = new Activity(11, 12);
arr[6] = new Activity(8, 10);
activitySelection(arr, n);
}
}

**Output**

```
Selected Activities are : (1, 3) (3, 4) (5, 9) (11, 12)
```

**Python Program to solve Activity Selection Problem using Greedy Algorithm**:

```
def activitySelection(arr, n):
```*# Sorting activities by finish time*
arr.sort(key = lambda x : x[1])
*# First activity will bealways selected*
i = 0
print(arr[i], end=' ')
for j in range(1, n):
*# If the current activity has start time >= finish time of previously selected*
*# activity, then select it*
if arr[j][0] >= arr[i][1]:
print(arr[j], end=' ')
i = j
arr = [[3, 4], [2, 5], [1, 3], [5, 9], [0, 7], [11, 12], [8, 10]]
n = len(arr)
print("Selected activities are :", end=' ')
*# Calling the selection function *
activitySelection(arr, n)

**Output**

```
Selected activities are : [1, 3] [3, 4] [5, 9] [11, 12]
```

**Complexity Analysis:**

**Complexity Analysis:**

```
Case 1:
When the provided list of activities is already sorted by finish time, then no need for sorting it again. Therefore, Time Complexity in such a case will be `O(n)`.
Case 1:
When the provided list of activities is not sorted, then we will have to either write a `sort()` function from scratch or we can use the in-built Standard Template Library function. Therefore, Time Complexity, in this case, will be `O(nlogn)`.
Space Complexity:`O(1)`, Since no Auxillary space is required.
```

### Approach 2: Count the maximum number of non-conflicting activities

**Intuition***This approach involves the use of dynamic programming, as this problem is a variation of Longest Increasing Subsequence (LCS)*. The intuition is to sort the given array of activities named`arr`

by start time, after which we can create an array named`dp`

, such that`dp[i]`

stores the count of maximum activities that can be performed without conflict.**Algorithm**The recursive way of completing the dp[i] after every i’th activity is:

```
dp[i] = arr[i] + {max(dp[j]), where j < i and arr[j].finish <= arr[i].start}
= arr[i], else
```

Let us take an example where sorted –

```
arr = {{0, 7}, {1, 3}, {2, 5}, {3, 4}, {5, 9}, {8, 10}, {11, 12}}
```

For the above example dp[] would be:

```
L[0]: {0, 7}
L[1]: {1, 3}
L[2]: {2, 5}
L[3]: {1, 3}, {3, 4}
L[4]: {1, 3}, {3, 4}, {5, 9}
L[5]: {1, 3}, {3, 4}, {8, 10}
L[6]: {1, 3}, {3, 4}, {5, 9}, {11, 12}
```

**Implementation**

**C++ Program to Count the maximum number of non-conflicting activities using Dynamic Programming**

```
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct Activity
{
int start, finish;
};
int activitySelection(vector<Activity> arr)
{
```*// sorting the activities in increasing order of their start time*
sort(arr.begin(), arr.end(),
[](Activity &x, Activity &y) {
return x.start < y.start;
});
*// dp[i] stores the maximum count of non-conflicting activities till i'th activity*
vector<int> dp(arr.size());
for (int i = 0; i < arr.size(); i++)
{
for (int j = 0; j < i; j++)
{
*// when `arr[j].finish` is less than equal to `arr[i].start`*
if (arr[j].finish <= arr[i].start && dp[i] < dp[j]) {
dp[i] = dp[j];
}
}
*// increment dp[i]*
dp[i]++;
}
*// return the maximum activity length in the list*
return *max_element(dp.begin(), dp.end());
}
int main()
{
*// arr storing the start and finish of all activities*
vector<Activity> arr = {{3, 4}, {2, 5}, {1, 3}, {5, 9}, {0, 7}, {11, 12}, {8, 10}};
cout << "The maximum number of non-conflicting activities are " << activitySelection(arr);
return 0;
}

**Output**

```
The maximum number of non-conflicting activities are 4
```

**Java Program to Count the maximum number of non-conflicting activities using Dynamic Programming**

```
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
```*// A class to store the start and finish time of the activities*
class Activity
{
public final int start;
public final int finish;
*// Constructor*
private Activity(int start, int finish)
{
this.start = start;
this.finish = finish;
}
public static Activity of(int a, int b)
{
*// calling constructor*
return new Activity(a, b);
}
}
class Main
{
public static int activitySelection(List<Activity> arr)
{
*// sorting the activities in increasing order of their start time*
Collections.sort(arr, Comparator.comparingInt(Activity -> Activity.start));
*// dp[i] stores the maximum count of non-conflicting activities till i'th activity*
int[] dp = new int[arr.size()];
for (int i = 0; i < arr.size(); i++)
{
for (int j = 0; j < i; j++)
{
*// when `arr[j].finish` is less than equal to `arr[i].start`*
if (arr.get(j).finish <= arr.get(i).start && dp[i] < dp[j]) {
dp[i] = dp[j];
}
}
*// increment dp[i] *
dp[i]++;
}
*// return the maximum activity length in the list*
return Arrays.stream(dp).max().getAsInt();
}
public static void main(String[] args)
{
*// Each pair stores the start and the finish time of an activity*
List<Activity> arr = Arrays.asList(
Activity.of(3, 4), Activity.of(2, 5), Activity.of(1, 3),
Activity.of(5, 9), Activity.of(0, 7), Activity.of(11, 12),
Activity.of(8, 10)
);
System.out.println("The maximum number of non-conflicting activities are " + activitySelection(arr));
}
}

**Output**

```
The maximum number of non-conflicting activities are 4
```

**Python Program to Count the maximum number of non-conflicting activities using Dynamic Programming**

```
def activitySelection(arr):
```*# sorting the activities in increasing order of their start time*
arr.sort(key=lambda x: x[0])
*# dp[i] stores the maximum count of non-conflicting activities till i'th activity*
dp = [0] * len(arr)
for i in range(len(arr)):
for j in range(i):
*# when `arr[j].finish` is less than equal to `arr[i].start`*
if arr[j][1] <= arr[i][0] and dp[i] < dp[j]:
dp[i] = dp[j]
*# increment dp[i]*
dp[i] = dp[i] + 1
*# return the maximum activity length in the list*
return max(dp)
*# arr storing the start and finish of all activities*
arr = [[3, 4], [2, 5], [1, 3], [5, 9], [0, 7], [11, 12], [8, 10]]
print('The maximum number of non-conflicting activities are', activitySelection(arr))

**Output:**

```
The maximum number of non-conflicting activities are 4
```

**Complexity Analysis**

```
Since we are using nested for-loops to traverse the list of `n` activities `arr`,
**Time Complexity** :$O(n^{2})$
While we are also using an array named `dp` to store the maximum number of non-conflicting activities,
**Therefore the Space Complexity approach for this approach is:** $O(n)$
```

### Approach 3: Print the maximum number of non-conflicting activities

**Intuition**

The approach for this section is the same as the previous one, but the difference here is that instead of printing the number of non-conflicting activities we have to print all these activities. Therefore, instead of doing`dp[i]++`

, we will be adding`arr[i]`

to`dp[i]`

for every i’th activity.**Implementation**

**C++ Program to Print the maximum number of non-conflicting activities using Dynamic Programming**

```
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
```*// Struct to store the start and finish time of activities.*
struct Activity
{
int start, finish;
};
void activitySelection(vector<Activity> arr)
{
*// sorting the activities in increasing order of their start time*
sort(arr.begin(), arr.end(),
[](Activity &x, Activity &y) {
return x.start < y.start;
});
*// dp[i] stores the maximum non-conflicting activities till i'th activity*
vector<vector<Activity>> dp(arr.size());
for (int i = 0; i < arr.size(); i++)
{
for (int j = 0; j < i; j++)
{
*// # when `arr[j].finish` is less than equal to `arr[i].start`*
if (arr[j].finish <= arr[i].start &&
dp[i].size() < dp[j].size()) {
dp[i] = dp[j];
}
}
*// adding arr[i] to dp[i]*
dp[i].push_back(arr[i]);
}
*// finding the vector having maximum size in dp*
vector<Activity> max;
for (auto &pair: dp)
{
if (max.size() < pair.size()) {
max = pair;
}
}
*// printing activity with start and finish time*
for (Activity &pair: max) {
cout << "{" << pair.start << ", " << pair.finish << "} ";
}
}
int main()
{
*// arr storing the start and finish of all activities*
vector<Activity> arr = {{3, 4}, {2, 5}, {1, 3}, {5, 9}, {0, 7}, {11, 12}, {8, 10}};
cout << "The maximum number of non-conflicting activities are ";
activitySelection(arr);
return 0;
}

**Output:**

```
The maximum number of non-conflicting activities are {1, 3} {3, 4} {5, 9} {11, 12}
```

**Java Program to Print the maximum number of non-conflicting activities using Dynamic Programming**

```
import java.util.*;
```*// A class to store the start and finish time of the activities*
class Activity
{
public int start, finish;
Activity(int start, int finish)
{
this.start = start;
this.finish = finish;
}
@Override
public String toString() {
return "(" + this.start + ", " + this.finish + ")";
}
}
class Main
{
public static void activitySelection(List<Activity> arr)
{
*// sorting the activities in increasing order of their start time*
Collections.sort(arr, Comparator.comparingInt(x -> x.start));
*// dp[i] stores the maximum non-conflicting activities till i'th activity*
List<List<Activity>> dp = new ArrayList<>();
for (var Activity: arr) {
dp.add(new ArrayList<>());
}
for (int i = 0; i < arr.size(); i++)
{
for (int j = 0; j < i; j++)
{
*// when `arr[j].finish` is less than equal to `arr[i].start`*
if (arr.get(j).finish <= arr.get(i).start && dp.get(i).size() < dp.get(j).size()) {
dp.set(i, new ArrayList<>(dp.get(j)));
}
}
*// adding arr[i] to dp[i]*
dp.get(i).add(arr.get(i));
}
*// finding the vector having a maximum size in dp*
List<Activity> max = dp.stream().max(Comparator.comparingInt(x -> x.size())).get();
*// printing maximum non conflicting activity with start and finish time*
System.out.print(max);
}
public static void main(String[] args)
{
*// Each pair stores the start and the finish time of an activity*
List<Activity> arr = Arrays.asList(new Activity(3, 4), new Activity(2, 5),
new Activity(1, 3), new Activity(5, 9),
new Activity(0, 7), new Activity(11, 12),
new Activity(8, 10));
System.out.print("The maximum number of non-conflicting activities are ");
activitySelection(arr);
}
}

**Output:**

```
The maximum number of non-conflicting activities are [(1, 3), (3, 4), (5, 9), (11, 12)]
```

**Python Program to Print the maximum number of non-conflicting activities using Dynamic Programming**

```
def activitySelection(arr):
```*# sorting the activities in increasing order of their start time*
arr.sort(key=lambda x: x[0])
*# dp[i] stores the maximum non-conflicting activities till i'th activity*
dp = [[] for _ in range(len(arr))]
for i in range(len(arr)):
for j in range(i):
*# when `arr[j].finish` is less than equal to `arr[i].start`*
if arr[j][1] < arr[i][0] and len(dp[i]) < len(dp[j]):
dp[i] = dp[j].copy()
*# adding arr[i] to dp[i]*
dp[i].append(arr[i])
*# finding the list having maximum size in dp*
ans = []
for k in dp:
if len(ans) < len(k):
ans = k
*# printing the list having maximum non-conflicting activities*
print(ans)
*# arr storing the start and finish of all activities*
arr = [[3, 4], [2, 5], [1, 3], [5, 9], [0, 7], [11, 12], [8, 10]]
print('Maximum non-conflicting activities are', end=' ')
activitySelection(arr)

**Output**

` Maximum non-conflicting activities are [[1, 3], [5, 9], [11, 12]]`

**Complexity Analysis**

`Since we are using nested for-loops to traverse the list of `n` activities `arr`, `

**Therefore the Time Complexity approach for this approach is:** $O(n^{2})$

While we are also using a matrix named `dp`

to store the maximum number of non-conflicting activities,

**Therefore the Space Complexity approach for this approach is:** $O(n^{2})$

## Conclusion

- At every step in the Greedy Approach we have to make a choice that looks best at the moment and can provide us with an optimal solution for that problem.
- Since we had to maximize the number of performed activities, we chose the activity that will finish first as that will leave us with the maximum time to process the remaining activities.
- Time and Space Complexity for the Greedy approach when the given set of activities are not sorted is
`O(nlogn)`

and`O(1)`

respectively. - This second approach involves the use of dynamic programming, as this problem was a variation of Longest Increasing Subsequence
**(LCS)**