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.