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.

5. If starting time of next activity is greater than or equal to the finishing time of last      performed activity then this activity will be selected.
6. Store it in array A.
7. Store the location of finishing time of this activity in k.
8. When all activity will has been checked then return A.

Here is my implemented code of Greedy Activity Selector::

#include<stdio.h>
int main()
{
int s[30],f[30],s1[30],f1[30],n,i,temp,j=1,a[30],t1,t2;
printf("How many activity:");
scanf("%d",&n);
printf("\nEnter starting times of all activity first,s:");
for(i=1;i<=n;i++)
scanf("%d",&s[i]);
printf("\nEnter finishing times of all activity ,f:");
for(i=1;i<=n;i++)
scanf("%d",&f[i]);
for(i=1;i<=n;i++)
s1[i]=s[i];
for(i=1;i<=n;i++)
f1[i]=f[i];
//Sorting Array

for(i=1;i<n;i++)
{
    if(f[i]>f[i+1])
    {
    temp=f[i]; f[i]=f[i+1]; f[i+1]=temp;
    temp=s[i]; s[i]=s[i+1]; s[i+1]=temp;
    i=0;
    }
    else if(f[i]==f[i+1])
    {
        if((f[i]-s[i])>(f[i+1]-s[i+1]))
        {
        temp=f[i]; f[i]=f[i+1]; f[i+1]=temp;
        temp=s[i]; s[i]=s[i+1]; s[i+1]=temp;
        i=0;
        }
    }
}

a[1]=1; //Step 2
temp=1;  // Step 3:: I used temp instead of K
//Starting of loop
for(i=2;i<=n;i++)
{
    if(s[i]>=f[temp])
    {
      a[++j]=i; // Step 6
      temp=i;   //Step 7
    }
}
/*As I've sorted all activity before,Following loop will generate the actual location of Activity.*/
for(i=1;i<=j;i++)
{
    t1=s[a[i]];t2=f[a[i]];
    for(temp=1;temp<=n;temp++)
    {
        if(t1==s1[temp] && t2==f1[temp])
        {
            a[i]=temp;
            break;
        }
    }
}
printf("\nThe maximum Activity can perform:");
for(i=1;i<=j;i++)
printf("\t%d",a[i]);
return 0;
}

Sample Input & Output::
How many activity:11
Enter starting times of all activity first,s:1 3 0 5 3 5 6 8 8 2 12
Enter finishing times of all activity ,f:4 5 6 7 9 9 10 11 12 14 16
The maximum Activity can perform:       1       4       8       11 
About this code: 
This code will also work if finished times are  not sorted. It will automatically  sort during compilation & generate correct result at last. Enjoy.Please Leave a comment ,if any problem.