Activity Selection Problem

admin / / Algorithms, Greedy Algorithms

© Parineeth M R

Question 53. Given the start time and end time of N activities, find the maximum number of activities that can be performed (Activity Selection problem)

We can find the maximum number of activities using the greedy approach as indicated below

1. Sort the activities based on their end times so that an activity with a smaller end time is placed before an activity with a larger end time.

2. Traverse through the sorted list and choose the activities that can be completed without any conflicts (the start and end time of a chosen activity should not overlap with the start and end time of another chosen activity)

C/C++


/*Function for comparing two elements. This function used while sorting*/
int cmp_function(const void *p1, const void *p2)
{
	struct activity *x = (struct activity *)p1;
	struct activity *y = (struct activity *)p2;

	if (x->end_time < y->end_time)
		return -1;
	else if (x->end_time == y->end_time)
		return 0;
	else 
		return 1;
}


void sort(struct activity a[], int length)
{
	qsort(a, length, sizeof(struct activity), cmp_function);
}


/*
a: array of activities, where each activity has a start time and end time
num_activities: number of elements in the array. Should be >= 1
selected: the indexes of the selected activities 
Return value: Maximum number of activities that can be performed
*/
int activity_selection(struct activity a[],  int num_activities, int selected[])
{
	int i, count, cur_time; 

	/*Sort the activities in non-decreasing order of their end time*/
	sort(a, num_activities);

	/*Keep a track of the current time as we process the activities*/
	cur_time = 0;
	count = 0;
	for (i = 0; i < num_activities; ++i) {
		/*Pick the activity whose start time is on or after current time*/
		if (a[i].start_time >= cur_time) {
			selected[count] = i;
			count++;

			/*Update the current time to the end time of the activity*/
			cur_time = a[i].end_time;
		}
	}

	return count;
}

Java


/*This class is used for comparing two elements during sorting*/
class ActivityComparator implements Comparator<Activity> {
	public int compare(Activity a, Activity b)	{

		if (a.endTime > b.endTime)
			return 1;
		else if (a.endTime == b.endTime)
			return 0;
		else
			return -1;
	}
}


/*
a: array of activities, where each activity has a start time and end time
Returns: ArrayList having indexes of the selected activities 
*/
public static ArrayList<Integer> activitySelection(Activity[] a) {
	ArrayList<Integer> selected = new ArrayList<Integer>(); 

	/*Sort the activities in non-decreasing order of their end time*/
	Arrays.sort(a, new ActivityComparator());

	/*Keep a track of the current time as we process the activities*/
	int curTime = 0;
	int i = 0;
	for (Activity curActivity : a) {
		/*Pick the activity whose start time is on or after current time*/
		if (curActivity.startTime >= curTime) {
			selected.add(i);

			/*Update the current time to the end time of the activity*/
			curTime = curActivity.endTime;
		}
		++i;
	}

	return selected;
}

Python


#a: list of activities, where each activity has a start time and end time
#Return value: list having the index of the selected activities 
def activity_selection(a) :
	#Sort the activities in non-decreasing order of their end time
	a.sort(key = lambda x: x.end_time)

	selected = [] 

	#Keep a track of the current time as we process the activities
	cur_time = 0

	for  i, cur_activity in enumerate(a):
		#Pick the activity whose start time is on or after current time
		if (cur_activity.start_time >= cur_time) :
			selected.append(i)

			#Update the current time to the end time of the activity
			cur_time = cur_activity.end_time

	return selected