~activity.~cpp

贪心算法实现活动选择问题——最短路径

// Activity.cpp: implementation of the Activity class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "Activity.h"
#include "iostream.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

Activity::Activity()
{
	num=0;
}

Activity::~Activity()
{
	delete a;
	delete sorted;
}

void Activity::Init_Activity()
{
	cout<<"请输入活动个数:";
	cin>>num;
	a=new act[num];
	sorted=new int[num];
	int i;
	for(i=0;i<num;i++)
	{
		cout<<"请输入活动"<<i+1<<"的开始时间:";
		cin>>a[i].start;
		cout<<"请输入活动"<<i+1<<"的结束时间:";
		cin>>a[i].finish;
		if(a[i].finish<a[i].start)
		{
			cout<<"活动时间错误!"<<endl;
			i--;
		}
		sorted[i]=i;
	}
	Sort_Activity();
}

void Activity::Sort_Activity()
{
	int i,j;
	for(i=0;i<num;i++)
		for(j=0;j<num-i-1;j++)
		{
			if(a[j].finish>a[j+1].finish)
			{
				act b;
				int  c;
				c=sorted[j];
				sorted[j]=sorted[j+1];
				sorted[j+1]=c;
				b.finish=a[j].finish;
				b.start=a[j].start;
				a[j].finish=a[j+1].finish;
				a[j].start=a[j+1].start;
				a[j+1].finish=b.finish;
				a[j+1].start=b.start;
			}
		}
}

void Activity::Activity_Select()
{
	int i,finish=a[0].finish;
	cout<<sorted[0]+1;
	for(i=1;i<num;i++)
	{
		if(a[i].start>=finish)
		{
			finish=a[i].finish;
			cout<<"->"<<sorted[i]+1;
		}
	}
	cout<<endl;
}