用贪心算法编程实现会场安排问题

一、问题阐述

假设在足够多的会场里安排一批活动，并希望用尽可能少的会场。设计一个有效的贪心算法进行安排。

二、解题思路

设有k个需要安排的活动，用 n 来表示需要占用的会场数；

1、用一个数组a[ i ]来存储该活动的状态（是否被安排；0表示未安排，1表示已安排）；

2、用两个数组start[ i ],end[ i ]分别来记录k个活动的开始、结束时间；（这里默认是按照结束时间排列的非减序列，如果题目给出的未按照此顺序排列，需要进行重新排列）

3、用一个邻接矩阵m[ i ][ j ]来存储各个活动之间的相容关系（如果 i 活动的开始时间 <= j 活动的结束时间则m[ i ][ j ] =m[ j ][ i ] =1 ;反之m[ i ][ j ] =m[ j ][ i ] =1）；

4、开始安排（按照顺序1,2,3……）：首先对活动1进行安排，在邻接矩阵的第一行中进行遍历，n+1，在满足m[ i ][ j ]=0且a[ j ]=0的条件下找到可以与活动1安排在同一会场的活动p,记录a[ p ]=1；继续……

三、代码分享

#include
#include 
#include
using namespace std;
int main()
{
	ifstream infile("E:/会场安排/input.txt", ios::in);
	ofstream outfile("E:/会场安排/output.txt", ios::app);
	//给定k个会场
	int k;
	int i, j;
	infile >> k;
	//创建一个一维数组记录该会场是否占用
	int* a = new int[k];
	for (i = 1; i <= k; i++)
		a[i] = 0;
	//创建两个数组，存放活动开始、结束时间
	int* start = new int[k];
	int* end = new int[k];
	for (i = 1; i <= k; i++)
	{
		infile >> start[i] >> end[i];
	}
	//创建一个邻接矩阵存放各个会场是否相容
	int** m = new int* [k];
	for (i = 1; i <= k; i++)
	{
		m[i] = new int[k];
	}
	//根据各个活动的开始、结束时间填写邻接矩阵
	m[1][1] = 0;
	for (i = 2; i <= k; i++)
	{
		for (j = 1; j <= k; j++)
		{
			if (start[i] < end[j]&&i!=j)
			{
				m[i][j] = 1;
				m[j][i] = 1;
			}
			else {
				m[i][j] = 0;
				m[j][i] = 0;
			}
		}
	}
	//按照顺序开始着色
	int n = 0;
	for (i = 1; i <= k; i++)
	{
		if (a[i] == 0)
			n++;
		a[i] = 1;
		for (j = 1; j <= k; j++)
		{
			if (m[i][j] == 1 || a[j] == 1) j++;
			else
			{
				a[j] = 1;
				i = j;
			}
		}
	}
	outfile<< n;
	infile.close();
	return 0;
}

四、结果展示 样例输入

样例输出