Greedy Algorithm and Activity selection problem

 

Greedy Algorithm and Activity selection problem

Greedy algorithm is used to solved greedy algorithm.Greedy algorithm may provide a solution that is close to optimal.Optimal solution can be obtained by making greedy choice.Optimal solutions contain optimal sub solutions.Solutions to sub problems of an optimal solution are optimal.

Greedy algorithm to find solution of these problems

• Activity selection problem.
• Knapsack problem.
• Constructing huffman codes.
• Travelling sales person problem.
• Minimum spanning tree.
• Prefix codes.

Activity Selection problem

Greedy algorithm provides a well designed and simple method for selecting a maximum size set of mutually compatible activities. If there are N activities. The activities share a resource which can be used by only one activity at a time.Example Lecture Hall.

Each activity i has  a starting time s and finish time f. Activities i and j are compatible if the interval  do not overlap.The activity selection problem selects the maximum size set of mutually compatible activities. 

The process of selecting the activity becomes faster if the input activities are in order by increasing finishing time.

                                     f1<=f2<=f3<=------------------<=fn

Algorithm 

Greedy-Activity-Selector(s,f)

Step 1: n<-length[s].

Step 2: A<-{1}

Step 3:J<-1

Step 4: for i <-2 to n

Step 5: do if S_i>=f_j

Step 6: then A<-A∪ {i}

Step 7: j<- i

Step 8: return 

Example

Given 10 activities with their start and finish time

S=<A1,A2,A3,A4,A5,A6,A7,A8,A9,A10>

S_i=<1,2,3,4,7,8,9,9,11,12>

f_j=<3,5,4,7,10,9,11,13,12,14>

Compute and schedule where the largest number of activities take place using greedy algorithm Activity selection method.

Solution

Arrange the activities in increasing order of finish time

Activity   A1         A3         A2        A4         A6       A5      A7     A9     A8    A10

Start          1            3           2           4           8           7        9       11      9       12               

Finish        3            4           5           7          9           10      11      12     13      14

Now schedule A1

Next select A3 because that activity is non-interfering A3(Start time)=A1(Finish time).

Skip A2 because interfering activity 

A2(start time)<A3(finish time).

Activity selected if next activity starting time >last activity finish time.

Next schedule activity A4

 That activity is non-interfering A4(Start time)=A3(Finish time).

Next schedule activity A6

 That activity is non-interfering A6(Start time)>A4(Finish time).

Skip A5 because interfering activity 

A5(start time)<A6(finish time).

Next schedule activity A7

 That activity is non-interfering A7(Start time)=A6(Finish time).

Next schedule activity A9

 That activity is non-interfering A9(Start time)=A7(Finish time).

Skip A8 because interfering activity 

A8(start time)<A9(finish time).

Next schedule activity A10

 That activity is non-interfering A10(Start time)=A9(Finish time).

So final Activity schedule using greedy algorithm 

<A1,A3,A4,A6,A7,A9,A10>