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

一、问题阐述

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

二、解题思路

设有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<iostream>
#include <fstream>
#include<iomanip>
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;
}

四、结果展示

样例输入

样例输出