Activity Selection Problem

This particular problem of activity selection falls under the Greedy Algorithms with are basically known for making greedy choice from a set of possible solution and we choose the solution that seems to be the best at the moment .

We in Greedy Algorithms choose the best solution for the moment from a set of probable solutions and we do the feasibility check of the solution which basically means that we check  for the Feasibility of our selected solution that if it satisfy all the constraints a possible solution is supposed to satisfy.If the solution passes this check we remove it from the previous set of probable solutions and add it to the new set Optimal solution.

General characteristics of Greedy Algorithm:

     1. FEASIBLE:

      In feasible we check wether it satisfies all the possible problem constraints or not, so

      as to obtain atleast one solution to our problem.

      2. OPTIMAL CHOICE:

      In this the choice should be the optimum which is selected from the current

      available feasible choice.

      3. UNALTERABLE:

      Once the choice is made at any subsequent step, the choice is not altered.

One such problem is the Activity Selection Problem in which we try to schedule one shared resource over a set of competing activities. 

Aim: To select and maximize the size of set of mutually compatible activities.

"Mutually Compatible" -The term means that the activities do not overlap each other and hence compatible to each other.

The activities about which we are talking here have two main attributes:

1.Starting time (si)

2.Finish time.(fi)

where si <=fi

The activities are mutually compatible when their start and finish time do not overlap. That means non of the activities in our final set of solution overlap each other in terms  of these attributes.

Suppose that activity i and j are compatible then they must satisfy the following statements:

• si>=fj  or
• sj>=fi

so we can rightly say that the activity selection problem is all about selecting a maximum sized set of mutually compatible activities.

In the greedy implementation of this problem we first sort the activities in the increasing order and construct of solution set.

f1<=f2<=f3<=....<=fn

This sorting procedure and then arranging in a form of array take the O(log n) time .

The Greedy implementation of activity selection problem takes takes O(n) time in worst case  for scheduling a n activities.

This implementation always selects the activity with the earliest finish time that can be legally scheduled.Thus we can say that it makes a greedy choice of solution by leaving as much probability as possible for the rest of the activities to be scheduled.Thereby maximizes the unscheduled time remaining.

Example:

Scheduling 7 examination activities to be performed in a single hall .

#include<iostream>
#include<conio.h>
using namespace std;
void main()
{
 int act[3][7],i,j,temp,start,a[7],k=1,min;

for(i=0;i<7;i++)
 a[i]=0;
for(i=0;i<7;i++)
 act[0][i]=i+1;
for(j=0;j<7;j++)
 {cout<<"\nEnter the starting time of "<<j+1<<" activity:";
 cin>>act[1][j];
 cout<<"Enter the finishing time of "<<j+1<<" activity:";
 cin>>act[2][j];
 }
for(i=0;i<7;i++)
 {min=act[2][i];
 start=act[1][i];
 temp=i;
 for(j=i+1;j<7;j++)
  {if(act[2][j]<min)
   {min=act[2][j];
   start=act[1][j];
   temp=j;
   }
  }
 act[2][temp]=act[2][i];
 act[1][temp]=act[1][i];
 act[2][i]=min;
 act[1][i]=start;
 }
a[0]=1;
i=0;
for(int m=1;m<7;m++)
 {if(act[1][m]>=act[2][i])
  {a[k]=m+1;
  k++;
  i=m;
  }
 }
cout<<"\The activities that can be performed is:";
for(i=0;a[i]!=0;i++)
 cout<<a[i]<<" ";
getch(); 

}