Activity Selection Problem

Greedy Algorithm

Share

In this video we will learn about Activity Selection Problem, a greedy way to find the maximum number of activities a person or machine can perform, assuming that the person or machine involved can only work on a single activity at a time.

Points to remember

  • For this algorithm we have a list of activities with their starting time and finishing time.
  • Our goal is to select maximum number of non-conflicting activities that can be performed by a person or a machine, assuming that the person or machine involved can work on a single activity at a time.
  • Any two activities are said to be non-conflicting if starting time of one activity is greater than or equal to the finishing time of the other activity.
  • In order to solve this problem we first sort the activities as per their finishing time in ascending order.
  • Then we select non-conflicting activities.

Problem

Consider the following 8 activities with their starting and finishing time.

Activity a1 a2 a3 a4 a5 a6 a7 a8
start 1 0 1 4 2 5 3 4
finish 3 4 2 6 9 8 5 5

Our goal is to find non-conflicting activities.

For this we follow the given steps

  1. sort the activities as per finishing time in ascending order
  2. select the first activity
  3. select the new activity if its starting time is greater than or equal to the previously selected activity
    REPEAT step 3 till all activities are checked

Step 1: sort the activities as per finishing time in ascending order

Sorted Activity a3 a1 a2 a7 a8 a4 a6 a5
start 1 1 0 3 4 4 5 2
finish 2 3 4 5 5 6 8 9

Step 2: select the first activity

Step 3: select next activity whose start time is greater than
or equal to the finish time of the previously selected activity

Pseudo Code


Set i = 0;		//pointing at first element
for j = 1 to n-1 do
  if start time of j >= finish time of i then
    Print j
    Set i = j

  endif

endfor

Code in C


#include <stdio.h>

struct Activity {
	char id[5];
	int start;
	int finish;
};

void activitySelection(Activity activities[], int n);

int main(void) {

	//activities
	Activity activities[8] = {
		{"a1", 1, 3},
		{"a2", 0, 4},
		{"a3", 1, 2},
		{"a4", 4, 6},
		{"a5", 2, 9},
		{"a6", 5, 8},
		{"a7", 3, 5},
		{"a8", 4, 5}
	};

	//number of activities
	int n = 8;

	activitySelection(activities, n);

	return 0;
}

void activitySelection(Activity activities[], int n) {
	//variables
	int i, j;

	Activity temp;

	//step 1
	//sort the activities as per finishing time in ascending order
	for(i = 1; i < n; i++) {
		for(j = 0; j < n - 1; j++){
			if(activities[j].finish > activities[j+1].finish) {
				temp = activities[j];
				activities[j] = activities[j+1];
				activities[j+1] = temp;
			}
		}
	}

	//sorted
	printf("Sorted activities as per finish time (ascending order)\n");
	printf("%10s %10s %10s\n", "Activity", "Start", "Finish");
	for(i = 0; i < n; i++) {
		printf("%10s %10i %10i\n", activities[i].id, activities[i].start, activities[i].finish);
	}

	//step 2
	//select the first activity
	printf("-----Selected Activities-----\n");
	printf("%10s %10s %10s\n", "Activity", "Start", "Finish");
	printf("%10s %10i %10i\n", activities[0].id, activities[0].start, activities[0].finish);

	//step 3
	//select next activity whose start time is greater than
	//or equal to the finish time of the previously selected activity
	i = 0;
	for(j = 1; j < n; j++) {
		if(activities[j].start >= activities[i].finish) {
			printf("%10s %10i %10i\n", activities[j].id, activities[j].start, activities[j].finish);
			i = j;
		}
	}
}

Output


Sorted activities as per finish time (ascending order)
  Activity      Start     Finish
        a3          1          2
        a1          1          3
        a2          0          4
        a7          3          5
        a8          4          5
        a4          4          6
        a6          5          8
        a5          2          9
-----Selected Activities-----
  Activity      Start     Finish
        a3          1          2
        a7          3          5
        a6          5          8

Recently Added