Wednesday, December 19, 2012

Greedy Algorithms-Activity Selection Problem Solution

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.
The Algorithm of This greedy Activity Selector::
GREEDY-ACTIVITY-SELECTOR(s, f)
  1. n=s.length   
  2. A={a1}     
  3. k=1;
  4. for m=2 to n
  5.   if s[m]>=f[k]
  6.      A=A U {a.m}
  7.      k=m
  8. return A
//This Algorithm is collected from Introduction to Algorithms by Cormen,Leiserson,Rivest,Stein Description Of This Algorithm:
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.
3. Store the location of finishing time of First activity.
4. then start the loop operation from next to last activities.