Activity Selection Problem

greedy.cpp

#include<bits/stdc++.h>

using namespace std;

// Greedy Algorithm
// https://en.wikipedia.org/wiki/Activity_selection_problem 

struct Workshop
{
	Workshop( int s, int d ) : start_time( s ), duration( d ), end_time( s + d ) {}
	int start_time, duration, end_time;
};

struct Available_Workshops
{
	Available_Workshops( int* start_time, int* duration, int n )
	{
		for( int i = 0; i < n; ++i )
		{
			works.push_back( Workshop( start_time[ i ], duration[ i ] ) );
		}
	}

	vector<Workshop> works;
};

Available_Workshops* initialize( int* start_time, int* duration, int n )
{
	return new Available_Workshops( start_time, duration, n );
}

bool myfunction( const Workshop& lhs, const Workshop& rhs )
{
	return lhs.end_time < rhs.end_time;
}

int CalculateMaxWorkshops( Available_Workshops* availworks )
{
	vector<Workshop>& works = availworks->works;
	sort( works.begin(), works.end(), myfunction );

	int maxWorkIndex = 0;
	int count = 1;
	for( int i = 1; i < works.size(); ++i )
	{
		if( works[ i ].start_time >= works[ maxWorkIndex ].end_time )
		{

			maxWorkIndex = i;
			++count;
		}
	}

	return count;
}

int main( int argc, char *argv[] ) {
	int n; // number of workshops
	cin >> n;
	// create arrays of unknown size n
	int* start_time = new int[ n ];
	int* duration = new int[ n ];

	for( int i = 0; i < n; i++ ) {
		cin >> start_time[ i ];
	}
	for( int i = 0; i < n; i++ ) {
		cin >> duration[ i ];
	}

	Available_Workshops * ptr;
	ptr = initialize( start_time, duration, n );
	cout << CalculateMaxWorkshops( ptr ) << endl;
	return 0;
}