# Activity Selection Problem

Posted in  Last updated on December 7, 2023

## Problem

Given pairs of integers denoting starting and ending time of each task. Find the maximum number of tasks a person can do, provided that he can only do one task at a time.

#### Sample Input

`(1, 2), (2, 2)`

#### Sample Output

```(1,2)
(2,2)```

### Approach

The algorithm follows a greedy approach. We can sort the tasks based on the ending time. Starting from the first task, if the starting time of the next task is greater than the ending time of the current task, a person can do that task. The approach takes O(NlogN) time due to sorting.

#### C++

```#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
usingnamespacestd;
structPair
{
int start, finish;
};
{
int k = 0;
unordered_set<int> Set;
Set.insert(0);
[](autoconst &x, autoconst &y) {
return x.finish < y.finish;
});
for (int i = 1; i < tasks.size(); i++)
{
{
Set.insert(i);
k = i;
}
}
for (int i: Set)
{
<< ")" << endl;
}
}
intmain()
{
{
{1, 2}, {2, 2}
};
return0;
}```

#### Output

```(2, 2)
(1, 2)```

#### Python

```defsolve(tasks):
k = 0
Set = set()
k = i
return Set
tasks = [(1, 2), (2, 2)]

#### Output

`[(1, 2), (2, 2)]`

#### Java

```import java.util.*;
import java.util.stream.Collectors;
classPair
{
privateint start, finish;
publicPair(int start, int finish)
{
this.start = start;
this.finish = finish;
}
publicintgetFinish() {
return finish;
}
publicintgetStart() {
return start;
}
@Override
public String toString() {
return"(" + getStart() + ", " + getFinish() + ")";
}
}
classMain
{
{
int k = 0;
Set<Integer> ans = new HashSet<>();
for (int i = 1; i < tasks.size(); i++)
{
{
k = i;
}
}
return ans.stream()
.collect(Collectors.toList());
}
publicstaticvoidmain(String[] args)
{
List<Pair> tasks = Arrays.asList(new Pair(1, 2), new Pair(2, 2));
`[(1, 2), (2, 2)]`