![]() ![]() ![]() As the activity 1 has starting time which is equal to the finish time of activity 0, it gets selected. Sorted by their finish time, the activity 0 gets selected. In this example, we take the start and finish time of activities as follows: When activities are not sorted by their finish time, the time complexity is O(N log N) due to complexity of sorting Example When activities are sorted by their finish time: O(N) Sort Activity by finish times stored in finish The algorithm of Activity Selection is as follows: Activity-Selection( Activity, start, finish) If we sort elements based on their starting time, the activity with least starting time could take the maximum duration for completion, therefore we won't be able to maximise number of activities. By induction on the number of choices made, making the greedy choice at every step produces an optimal solution, so we chose the activity which finishes first. ![]() This is the intuition that greedily choosing the activity with earliest finish time will give us an optimal solution. So, choosing the activity which is going to finish first will leave us maximum time to adjust the later activities. Our objective is to complete maximum number of activities. at every step, we can make a choice that looks best at the moment to get the optimal solution of the complete problem. The problem statement for Activity Selection is that "Given a set of n activities with their start and finish times, we need to select 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." The Activity Selection problem follows Greedy approach i.e. Suprising, if we use a Dynamic Programming approach, the time complexity will be O(N^3) that is lower performance. Modifications of this problem are complex and interesting which we will explore as well. ![]() Activity Selection problem is a approach of selecting non-conflicting tasks based on start and end time and can be solved in O(N logN) time using a simple greedy approach. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |