活动安排问题-贪心算法

#include "stdafx.h"
#include "iostream"
#include <algorithm> 
#define NUM 100
using namespace std;

struct action
{
	int start;
	int end;
	int id;
}a[1000];

int cmp(const action &a,const action &b)
{
	if(a.end>b.end)
		return false;
	else
		return true;
}

void GreedySelector(int n,action a[],bool b[])
{
	b[1]=true;
	int preEnd=1;
	for(int i=2;i<n;i++)
	{
		if(a[i].start<a[preEnd].end)
		{
			b[i]=true;
			preEnd=i;
		}
	}
}

int _tmain(int argc, _TCHAR* argv[])
{

	int n;
	cin>>n;
	bool b[NUM]={false};
	for(int i=1;i<=n;i++)
		cin>>a[i].id>>a[i].start>>a[i].end;
	sort(a,a+n+1,cmp);
	GreedySelector(n,a,b);
	cout<<"被安排的活动序号：";
	for(int i=1;i<=n;i++)
		if(b[i])
			cout<<a[i].id<<" ";
	cout<<endl;
	system("pause");
	return 0;
}