Greedy Algorithm is an algorithm that let you to get a solution of a given problem by checking every item. It select the next item which brings optimal benefit at that moment.
Greedy Activity Selection Problem is the most common problem to learn the simple basic of Greedy Algorithm.
Now I would discuss about it::
You are given n activities with their start and finish times. you have to find out the maximum number of activities that can be performed by a single person.One thing should keep in mind that a person can only work on a single activity at a time.
1. the number of activities
2. To obtain line 2 of above algorithm you have to do some work.
4. then start the loop operation from next to last activities.
Greedy Activity Selection Problem is the most common problem to learn the simple basic of Greedy Algorithm.
Now I would discuss about it::
You are given n activities with their start and finish times. you have to find out the maximum number of activities that can be performed by a single person.One thing should keep in mind that a person can only work on a single activity at a time.
The Algorithm of This greedy Activity Selector::
GREEDY-ACTIVITY-SELECTOR(s, f)- n=s.length
- A={a1}
- k=1;
- for m=2 to n
- if s[m]>=f[k]
- A=A U {a.m}
- k=m
- return A
1. the number of activities
2. To obtain line 2 of above algorithm you have to do some work.
- First you have to sort all activities with respect to finishing time in ascending order.
- Then Select the First Activities(It must be done by person as it will finish first.) & store it in the first index of Array A.
4. then start the loop operation from next to last activities.