Write an algorithm for activity selection problem using greedy approach with suitable example.

Q.1 

Algorithm:

Greedy_Act_sel(S,F)

{

            Nßlength[S]

            Aß{a}

            Iß1

            for(mß2 to n)

            {

                        If(Sm>Fi)then

                                    AßA U {am}

                                    Ißm

            }

            return A;

}

Example:-consider following set of activities the set of activities sorted in ascending order.

i	1	2	3	4	5	6	7	8	9	10	11
si	1	3	0	5	3	5	6	8	8	2	12
fi	4	5	6	7	8	9	10	11	12	13	14

Step 1: Sort f_i into non decreasing order. After sorting, f₁ £ f₂ £ f₃ £ … £ f_n.

Step 2: Add the next activity i to the solution set if i is compatible with each in the solution set.

Step 3: Stop if all activities are examined. Otherwise, go to step 2.

              From the above set first of all we will select i1.the finish time of i1 is 4

                                                I1->          si=1         Fi=4

So add in the list {i1} then select the next activity whose starting time is greater than i1

                                                I4->       si=5   Fi=7

So at that way finally we get solution set is {1, 4, 8, 11}

Time complexity:  O(nlogn)