Activity Selection Problem - Greedy Algorithm
What is Activity Selection Problem? We are given 'n' activities with their start and finish times and we have to select the maximum number of activities that can be performed by a single person, assuming that the person can only work on a single activity at a time. Activity A1 A2 A3 A4 A5 A6 Start Time 0 3 1 5 5 8 End Time 6 4 2 8 7 9 How are we gonna solve this Activity Selection Problem? [Time Complexity - O(nlogn) Space Complexity - O(n)] As we want to cover the maximum number of tasks, we should complete all those tasks first that finish first. So our focus is going to be on the end time of tasks. 1. Sort the tasks by the end time 2. Always pick the first task and initialize a variable prevTaskTime = end time of the first task 3. For all other tasks: 4. if the current task...