C program for activity selection problem

#The activity selection problem is a problem given a set of activities and their start and end times. We need to find all the activities that a person can perform performing a single activity at once.

This problem specifies a greedy algorithm to choose the next activity to perform. Let’s first understand greedy algorithm.

Greedy Algorithm is an algorithm that attempts to find a solution to a problem by finding a solution step by step. To choose the next step, the algorithm also selects the step that seems most promising, i.e. one that immediately leads to an optimized solution compared to the rest. The greedy algorithm is used to solve optimization problems as it attempts to find the most optimal solution for the next intermediate step, leading to the optimal solution to the entire problem.

Although the greedy algorithm is a good solution, there are some problems that prevent it from being applied. For example, the 0-1 knapsack cannot be solved using a greedy algorithm.

Algorithm

Some standard greedy algorithms are -

1) Dijkstrata’s Shortest Path
2) Minimum Spanning Tree (MST) {prim’s and kruskal’s}
3) Huffman coding

Inactivity selection problem, we are given n problems with start and end time. We need to choose the maximum number of activities that a person can perform, assuming that he can only perform one activity at a time.

There are 3 activities, sorted by their end time,

Start = [1 , 5 , 12 ]
End = [10, 13, 23]

Here, one can perform up to two activities. The activities that can be performed are [0, 2].

Example

Demonstration

#include<stdio.h>
int main(){
   int start[] = {1 , 5 , 12};
   int finish[] = {10, 13, 23};
   int activities = sizeof(start)/sizeof(start[0]);
   int i, j;
   printf ("Following activities are selected \t");
   i = 0;
   printf("%d\t", i);
   for (j = 1; j < activities; j++){
      if (start[j] >= finish[i]){
         printf ("%d ", j);
         i = j;
      }
   }
   return 0;
}

Output

Following activities are selected 0 2

The above is the detailed content of C program for activity selection problem. For more information, please follow other related articles on the PHP Chinese website!