会议安排问题C++贪心算法

• • 1. 实现活动安排问题的贪心算法
  • 2.问题建模；
  • 3.算法设计；
  • 4.编码实现；
  • 5.测试数据；
  • 6.程序运行结果；
  • 7.算法分析；

1.认真审阅题目，明确题目的已知条件和求解的目标；
给定n个会议的开始时间和结束时间，求解在尽可能的选择更多的会议来使用资源

（1）初始化：将n各会议的开始时间存储在数组B中，将n各会议的结束时间存储在十足E中，且按照结束时间的非减排序；e1 <= e2 ……,数组B需要做相应的调整，采用集合A来存储问题的解，即所选择的会议集合，会议i如果在集合A中，当且仅当A[i] = true
（2）根据贪心策略，算法GreedySelector首先选择会议1，即当A[1] = true
（3）依次扫描每一个会议，如果会议i的开始时间不小于最后一个选入集合A中的会议的结束时间，即会议i与A中会议相容，即将会议i加入集合A中，否则，放弃会议i,继续检查下一个会议与集合A中会议的相容性

#include 
using namespace std;
struct node
{
	int start, end;
}greedytime[10010];
int cmp(node a, node b){
	return a.end < b.end;
}
void GreedySelector(int n, struct node time[], bool A[]){
	//E中存放的是结束时间，按照非减序排列，B中做相应的调整
	int i, j;
	A[1] = true;
	int begin = time[1].end;
	j = 1;//首先将第一个 会议放入A中 
	i = 2;//用数组中第二个元素的开始时间与第一个的结束时间相比较，判断是否相容 
	while(i <= n){
		if(time[i].start >= begin){
			A[i] = true;//如果相容，则将该会议加入A数组中 
			begin = time[i].end;
		}
		else
		{
			A[i] = false;
		}
		i++;
	} 
} 

int main(){
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> greedytime[i].start;//输入开始时间 
		cin >> greedytime[i].end;//输入结束时间 
	}
	bool A[10010];
	int count = 0;
	sort(greedytime,greedytime+n,cmp); 
	GreedySelector(n,greedytime,A);
	for(int i = 1; i <= n; i++){
		if(A[i] == true)
		{
			count++; 
		} 
	}
	cout << "可以安排" << count << "个会议" << endl;
	return 0;
}

第一组：
输入：

3
1 5
2 8
6 8

输出：可以安排两个会议

第二组：
输入：
11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

输出： 可以安排4个会议

从GreedySelector算法的描述中可以看出，该算法的时间主要消耗在将搞个活动按结束时间从小到大排序操作。若采用快速排序算法进行排序，算法的时间复杂性为O（nlogn）。显然该算法的空间复杂性是常数阶S（N） =
O（1）