Category: Greedy Algorithms

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

Maximum profit given stock prices

admin / / Algorithms, Greedy Algorithms

© Parineeth M R

Question 52. Given a set of stock prices over a period of time, find the maximum profit possible by buying and selling the stocks. For instance, if the stock prices are 100, 90, 200, 20, 70, 150, 10 and 40, then the maximum profit = 150 – 20 = 130

If we use a brute force approach, then we will compare every pair of numbers to find the maximum profit possible. This requires O(n2) operations. However using the greedy approach we can solve the problem in O(n). The main idea of the greedy approach is that it is sufficient to maintain the minimum stock price that we have encountered so far as we traverse the stock prices.

The procedure is as follows: as we traverse the stock price list, subtract the minimum stock price seen so far from the current stock price to figure out the profit. If the profit is greater than the maximum profit so far, then update the maximum profit.

The working of the algorithm on the stock prices {100, 90, 200, 20, 70, 150, 10, 40} is given below. The minimum stock price is initialized to the first element 100. The max profit is initialized to 0. We start from the second stock price onwards.

C/C++


/*
stock_price: array of stock price values
n: number of elements in the array
Return value: maximum profit possible
*/
int find_max_profit(int stock_price[], int n)
{
	int i, min_stock_price, cur_profit, max_profit;

	max_profit = 0;
	if (n <= 1)
		return max_profit;

	min_stock_price = stock_price[0];

	for (i = 1; i < n; ++i) {
		
		cur_profit = stock_price[i] - min_stock_price;

		if (cur_profit > max_profit)
			max_profit = cur_profit;

		if (stock_price[i] < min_stock_price)
			min_stock_price = stock_price[i];
	}

	return max_profit;
}

Java


/*
stockPrice: array of stock price values
Return value: maximum profit possible
*/
public static int findMaxProfit(int[] stockPrice) {
	int n = stockPrice.length;

	int maxProfit = 0;
	if (n <= 1)
		return maxProfit;

	int minStockPrice = stockPrice[0];

	for (int i = 1; i < n; ++i) {
	
		int curProfit = stockPrice[i] - minStockPrice;

		if (curProfit > maxProfit)
			maxProfit = curProfit;

		if (stockPrice[i] < minStockPrice)
			minStockPrice = stockPrice[i];
	}

	return maxProfit;
}

Python


#stock_price: list of stock price values
#Return value: maximum profit possible
def find_max_profit(stock_price) :
	n = len(stock_price)

	max_profit = 0
	if (n <= 1):
		return max_profit

	min_stock_price = stock_price[0]

	for  i in range(1, n):
		cur_profit = stock_price[i] - min_stock_price

		if (cur_profit > max_profit):
			max_profit = cur_profit

		if (stock_price[i] < min_stock_price):
			min_stock_price = stock_price[i]
	
	return max_profit