Activity Selection Problem

                      Resource:

GeeksForGeeks

Activity Selection Problem

techiedelight

                 Implementation: 01

	/*
	1) Sort the activities according to their finishing time
	2) Select the first activity from the sorted array and print it.
	3) Do following for remaining activities in the sorted array.
	…….a) If the start time of this activity is greater than or equal to the finish time of previously selected activity then select this activity and print it.
	it is assumed that the activities are already sorted according to their finish time.
	*/
	#include <bits/stdc++.h>
	using namespace std;
	#define INF 1<<30
	#define MAX 10005
	#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	typedef long long ll;
	void printMaxActivities(int s[], int f[], int n)
	{
	int i,j;
	i = 0;
	cout << "Following activities are selected:\n";
	cout << i << " ";
	for(j = 1; j < n; j++){
	if(s[j] >= f[i]){
	cout << j << " ";
	i = j;
	}
	}
	}
	int main()
	{
	FASTIO
	///*
	//double start_time = clock();
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	freopen("error.txt", "w", stderr);
	#endif
	//*/
	int start[] = {1, 3, 0, 5, 8, 5};
	int finish[] = {2, 4, 6, 7, 9, 9};
	int n = sizeof(start)/sizeof(start[0]);
	printMaxActivities(start, finish, n);
	return 0;
	//double end_time = clock();
	//printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
	return 0;
	}

view raw ActivitySelection1.cpp hosted with ❤ by GitHub

                 Implementation: 02

	/*
	1) Sort the activities according to their finishing time
	2) Select the first activity from the sorted array and print it.
	3) Do following for remaining activities in the sorted array.
	…….a) If the start time of this activity is greater than or equal to the finish time of previously selected activity then select this activity and print it.
	*/
	#include <bits/stdc++.h>
	using namespace std;
	#define INF 1<<30
	#define MAX 10005
	#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	typedef long long ll;
	bool cmp( const pair<int,int>& x, const pair<int,int>& y)
	{
	return (x.second < y.second);
	}
	void printMaxActivities(vector<pair<int,int > > const &v)
	{
	// cerr << "enter-------\n";
	int k = 0;
	set<int>ans;
	ans.insert(0);
	for(int i = 1; i < v.size(); i++){
	if(v[i].first >= v[k].second){
	ans.insert(i);
	k = i;
	}
	}
	for(auto i: ans){
	cout << "{"<<v[i].first << " , "<<v[i].second << "}\n";
	}
	}
	int main()
	{
	FASTIO
	///*
	//double start_time = clock();
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	freopen("error.txt", "w", stderr);
	#endif
	//*/
	vector<pair<int,int> >activity;
	int n;
	cin >>n;
	for(int i = 0; i < n; i++){
	int start, finish;
	cin >> start >> finish;
	activity.push_back({start, finish});
	}
	//for(int i = 0; i < n; i++)cerr << activity[i].first <<" "<<activity[i].second<<endl;
	sort(activity.begin(),activity.end(),cmp);
	//for(int i = 0; i < n; i++)cerr << activity[i].first <<" "<<activity[i].second<<endl;
	printMaxActivities(activity);
	//double end_time = clock();
	//printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
	return 0;
	}

view raw ActivitySelection2.cpp hosted with ❤ by GitHub

Share: