Activity Selection Problem (DP-16)

You are given a set of activities and their start and end times. You need to find out the maximum number of activities that a single person can perform assuming that the person can only perform one activity at a time and print all of them.

Sample Input:

{
{1, 4}, {3, 5}, {0, 6}, {5, 7}, {3, 8}, {5, 9},
{6, 10}, {8, 11}, {8, 12}, {2, 13}, {12, 14}
};

Expected Output:

{1, 4}
{5, 7}
{8, 11}
{12, 14}

Explanation: The maximum number of non overlapping activities that a person can perform is 4.

Algorithm:

The problem can be solved using dynamic programming as it has both optimal substructure and overlapping sub-problem. The problem is a variation of Longest Increasing Subsequence. We suggest you to take a look into that before solving this problem.

  1. We sort the activities based on the increasing order of their starting times.
  2. Create a 2D array DP to store the result of the sub problems. DP [i] will store a list of activities which contains the maximum number of activities that can be performed by the person from the set of activities Activities [0 … i].
  3. We iterate for all the activities and for each activity, we consider all the activities before that activity and if the activity has starting time less than the current activity and the size of maximum number of activities for that sub-problem is greater than the current size, we update the current list of activities with that particular list and add the current activity. This will become more clear with the code.
  4. We return the list which has the largest size.
#include <bits/stdc++.h>
using namespace std;

vector<pair<int, int>> helper(vector<pair<int, int>> acts){
	sort(acts.begin(), acts.end(), [](pair<int, int> p1, pair<int, int> p2){
		if(p1.first<p2.first){
			return p1.second < p2.second;
		}
		return p1.first < p2.first;
	});
	vector<vector<pair<int, int>>> ans(acts.size());
	for(int i=0; i<acts.size(); i++){
		for(int j=0; j<i; j++){
			if(acts[j].second < acts[i].first && ans[j].size()>ans[i].size()){
				ans[i] = ans[j];
			}
		}
		ans[i].push_back(acts[i]);
	}
	vector<pair<int, int>> ret;
	for(auto v:ans){
		if(v.size()>ret.size()){
			ret = v;
		}
	}
	return ret;
}



int main(){
	vector<pair<int, int>> acts = {
		{1, 4}, {3, 5}, {0, 6}, {5, 7}, {3, 8}, {5, 9},
		{6, 10}, {8, 11}, {8, 12}, {2, 13}, {12, 14}
	};

	vector<pair<int, int>> ans = helper(acts);
	for(auto p:ans){
		cout<<"{"<<p.first<<", "<<p.second<<"}"<<endl;
	}
	return 0;
}

Also, check out another popular interview problem House Robber Problem.

2 comments

Leave a Reply

Your email address will not be published.