Activity Selection Problem
This problem can be solved using the Greedy Approach.
Goal: Given n activities with their start and finish times, find the maximum number of activities that a single person can perform, given that he/she can perform only one activity at a time.
Solution: A2, A3
- Sort the activities according to their finish times
- Print the first activity in the sorted array
- For the rest of the activities in the array: print the activity if its start time is greater than or equal to the finish time of the previous task
In the above example:
Sorting according to finish times:
Now print A2.
Then, check if A1 has start time >= finish time of A2. It doesn't. So, check the same for A3.
Since A3 has start time >= finish time of A2, print A3.
Output: A2, A3
Time Complexity: O(n) for sorted input, O(nlgn) for unsorted input.