Given **N** activities with their **start** and **end** time.

The task is to select/print maximum number of **non-conflicting** activities that can be performed by a single person, given that the person can handle only one activity at a time.

##### Example 1: Activity Selection Problem

Input: (10,20), (12,30), (20,52)

**Output: (10,20), (20,52)**

##### Example 2: Activity Selection Problem

Input: (1,5), (2,7), (6,7), (8,11), (8,9)

**Output: (1,5), (6,7), (8,9)**

## Solutions

### Method 1: Greedy Algorithm

The greedy algorithm suggest to always **pick the next activity whose finish time is least** among the remaining activities and the start time is more than or equal to the finish time of the last selected activity.

**1)** Sort the activities according to their finishing time.

**2) **Select the first activity from the sorted array and print it.

**3)** For the remaining activities in the sorted array - If the start time of this activity is greater than or equal to the finish time of the previously selected activity then select this activity and print it.

##### Complexity

**O(n log n)**time if input activities are not sorted already and takes

**O(n)**time when it is given that input activities are sorted.