main.cpp

求解活动安排问题.设有N个活动,其中每个活动都要求使用相同的一种资源,而在同一时间内只有一个活动能使用这一资源,每个活动也有要求使用该资源的开始时间和截止时间,如果两个活动使用统一资源的时间不冲突,那

#include <iostream.h>

int NumOfAcitivity = 0;

template <class Type>
class Active
{
	friend void sort(Active<Type> *a, int n);
	friend void GreedySelector(Active<Type> *a, int n);
private:
	bool IsSelected;
	int ItemNum;
	Type startTime;
	Type finishTime;
public:
	Active();
	void run();
	bool CheckActivity();
	bool operator < (const Active<Type>& a);
	Active<Type> operator = (const Active<Type>& a);
};

template<class Type>
Active<Type>::Active()
{
	IsSelected = false;
	ItemNum = -1;
	startTime = 0;
	finishTime = 0;
}

template <class Type>
bool Active<Type>::operator < (const Active<Type>& a)
{
	return this->finishTime < a.finishTime;
}

template <class Type>
Active<Type> Active<Type>::operator = (const Active<Type>& a)
{
	this->IsSelected = a.IsSelected;
	this->ItemNum = a.ItemNum;
	this->startTime = a.startTime;
	this->finishTime = a.finishTime;
	return *this;
}

template<class Type>
bool Active<Type>::CheckActivity()
{
	return this->startTime < this->finishTime;
}

template<class Type>
void sort(Active<Type> *a, int n)
{
	for(int i = 0; i < n - 1; i++)
	{
		int k = i;
		for(int j = i + 1; j < n; j++)
		{
			if(a[j] < a[k])
				k = j;
		}
		if(i != k)
		{
			Active<Type> temp;
			temp = a[i];
			a[i] = a[k];
			a[k] = temp;
		}
	}
}

template<class Type>
void GreedySelector(Active<Type> *a, int n)
{
	a[0].IsSelected = true;
	int j = 0;
	for(int i = 1; i < n; i++)
	{
		if(a[i].startTime >= a[j].finishTime)
		{
			a[i].IsSelected = true;
			j = i;
		}
		else
			a[i].IsSelected = false;
	}
}

template<class Type>
void Active<Type>::run()
{
	cout << "*******************************************************************" << endl;
	cout << "		   The Arrangement of Activities.        " << endl;
	cout << "*******************************************************************" << endl;
	cout << endl << "Please input the number of activities at first: ";
	cin >> NumOfAcitivity;
	Active<Type> *a = new Active<Type>[NumOfAcitivity];
	cout << "Then, please continue to input the starting and finishing time of each activity:" << endl;
	cout << "The item\tThe starting time\tThe finishing time\n";
	for(int i = 0; i < NumOfAcitivity; i++)
		cin >> a[i].ItemNum >> a[i].startTime >> a[i].finishTime;

	sort(a, NumOfAcitivity);
	GreedySelector(a, NumOfAcitivity);
	for(i = 0; i < NumOfAcitivity; i++)
		if(!(a[i].CheckActivity()))
		{
			cout << "One of the activities you have inputted is illegal." << endl;
			return;
		}

	cout << endl << "The result of arrangement is:" << endl;
	for(i = 0; i < NumOfAcitivity; i++)
		if(a[i].IsSelected)
			cout << a[i].ItemNum << '\t' << a[i].startTime << '\t' << a[i].finishTime << endl;
}

void main()
{
	Active<int> a;
	a.run();
}