Greedy Algorithm’s: activity selection.

We may never appreciate being greedy, we may still be greedy and be trolled or insulted by others for being so.But in coding we got to be greedy in some cases.And guess what? Its quite beneficial to be so in many cases.To be more specific being greedy can actually help your poor computer(if it’s so)compute faster and better.

Activity

Now in timeline we accomplish a list of task’s . To be accurate, i must say that we plan a schedule for our task’s , but we aren’t always successful in doing it all.Basically Activity is a singular task we think to complete.

Greedy analysis

Lets just directly start with an example, i believe the best way to understand any topic.

Now lets assume that we are given some jobs along with their starting time (s) and finishing time(f).

so the activity table may look something like this.

Now we see that the finishing time of the activities (a) aren’t sorted.So we should make sure that the finishing times should be sorted .Now if we sort the table then it would look something like this.

After we are done as such, there’s only the code part that we need to worry.

A critical point to remember is that the first activity of every sorted array must always be printed.And the greedy approach must start right from the next activity.Now this is logical as in a sorted array the first element has the latest deadline or finishing time.

If the start time of this activity is greater than or equal to the finish time of previously selected activity then select this activity and print it.

The code

#include<stdio.h>

// Prints a maximum set of activities that can be done by a single
// person, one at a time.
// n → Total number of activities
// s[] → An array that contains start time of all activities
// f[] → An array that contains finish time of all activities
void printMaxActivities(int s[], int f[], int n)
{
int i, j;

printf (“Following activities are selected n”);

// The first activity always gets selected
i = 0;
printf(“%d “, i);

// Consider rest of the activities
for (j = 1; j < n; j++)
{
// If this activity has start time greater than or
// equal to the finish time of previously selected
// activity, then select it
if (s[j] >= f[i])
{
printf (“%d “, j);
i = j;
}
}
}

// driver program to test above function
int main()
{
int s[] = {0, 1, 4, 3, 1};
int f[] = {2, 3, 4, 6, 6};
int n = sizeof(s)/sizeof(s[0]);
printMaxActivities(s, f, n);
return 0;
}

so as you can see, the code’s just a normal use of arrays and comparing the elements of the array.

But let me tell you that in cases when there are numerous activities and we have to classify and select them, this greedy method can save your computer from being in very drastic trouble of time limit being exceeded etc.

SO BE WISE BE GREEDY.