# Activity Selection Problem

Objective: The activity selection problem is a combinatorial optimization problem concerning the selection of non-conflicting activities to perform within a given time frame, given a set of activities each marked by a start time (si) and finish time (fi). The problem is to select the maximum number of activities that can be performed by a single person or machine, assuming that a person can only work on a single activity at a time.

Non-Conflicting activities: Let’s consider there are N activities and for each activity, there is a start s time and end time f for that activity. Two activities i and j are said to be non-conflicting if si ≥ fj or sj ≥ fi.

Example:

```Given Activities: [[1, 3], [2, 5], [0, 7], [6, 8], [9, 11], [10, 12]]
Selected Activities:
[1, 3] [6, 8] [9, 11]

Given Activities: [[1, 3], [2, 5]]
Selected Activities:
[1, 3]

Given Activities: [[0, 7], [1, 3], [4, 5]]
Selected Activities:
[1, 3] [4, 5]
```

Algorithm: Greedy

1. Sort all the activities according to their end time.
2. Select the first activity and note the end time, call it as current_end.
3. Now iterate through the rest of the activities. For each current_activity
1. If start time of current_activity > current_end
1. Select current_activity.
2. Update current_end = end time of current_activity.
2. Else
1. Ignore the current_acitvity.

Time Complexity: O(nlogn)

Complete Code:

Output:

```Given Activities: [[1, 3], [2, 5], [0, 7], [6, 8], [9, 11], [10, 12]]
Selected Activities: [[1, 3], [6, 8], [9, 11]]
```

This site uses Akismet to reduce spam. Learn how your comment data is processed.