Activity Selection Problem using Greedy algorithm

algorithm
greedy-algorithm
activity-selection-algorithm
(Team) #1

Our objective is to complete maximum number of activities. So, choosing the activity which is going to finish first will leave us maximum time to adjust the later activities. This is the intuition that greedily choosing the activity with earliest finish time will give us an optimal solution. 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. 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.

Read this article to learn about Activity Selection Problem using Greedy algorithm in depth

Have a doubt or thought? Join the discussion now


This is a companion discussion topic for the original entry at http://iq.opengenus.org/activity-selection-problem-greedy-algorithm/
0 Likes