＜算法＞贪心策略设计并解决会场安排问题

🎉 每个不曾起舞的日子都是对生命的辜负

🎉写在前面

期末考试邻近，为了更好的应对《算法设计与分析》这门课程，我把书上以及老师讲过的案例都详细的做一个重现及解剖，让你熟记每一个潜在的考点，希望能给大家帮助。

🎉目录

问题描述

 贪心策略

 算法设计

代码实现

选择结构体

随机输入会议

按结束时间排序

最终会议确定

结束语

问题描述

设有n个会议的集合C={1,2,…,n}，其中每个会议都要求使用同一个资源（如会议室），而在同一时间内只能有一个会议使用该资源。每个会议i都有要求使用该资源的起始时间bi和结束时间ei，且bi < ei 。如果选择了会议i使用会议室，则它在半开区间[bi, ei)内占用该资源。如果[bi, ei)与[bj , ej)不相交，则称会议i与会议j是相容的。会场安排问题要求在所给的会议集合中选出最大的相容活动子集，也即尽可能地选择更多的会议来使用资源。

 贪心策略

1、选择最早开始时间且不与已安排会议重叠的会议

2、选择使用时间最短且不与已安排会议重叠的会议

3、选择具有最早结束时间且不与已安排会议重叠的会议

这里我选取第三种方法 

 算法设计

设有11个会议等待安排，用贪心法找出满足目标要求的会议集合。这些会议按结束时间的非减序排列如表所示

11个会议按结束时间的非减序排列表：

代码实现

#include 
#include "会场安排.h"
#define n 11
struct meeting{
	int B;//开始时间
	int E;//结束时间
};
using namespace std;
int main()
{
	meeting M[n] = { {8,11}, {8,12}, {2,13}, {12,14}, {1,4},
		           {3,5}, {0,6}, {5,7}, {3,8}, {5,9}, {6,10} };
	for(int i=0;i allowedTime) {
			j++;
			cout