C++ 会议安排(贪心算法)_编程题 日常工作中总是有各种会议的冲突,如何在有限的工作时间内

描述：

学校的小礼堂每天都会有许多活动，有时间这些活动的计划时间会发生冲突，需要选择出一些活动进行举办。
小刘的工作就是安排学校小礼堂的活动，每个时间最多安排一个活动。现在小刘有一些活动计划的时间表，
他想尽可能的安排更多的活动，请问他该如何安排。

---

简短理解题意：在不发生冲突的情况下，一天最多可以安排多少个会议？

目标：在有限的时间内，尽可能多地安排会议。

---

贪心策略：

1.选最早开始的会议(缺点：会议可能结束的晚，也就是持续的时间会很长)

2.选结持续时间最短的会议(缺点：会议可能开始的很晚)

3.选择最早结束的会议

---

算法设计思路：

• 1.按照会议的结束时间升序排序(也就是选择结束时间最早的)
  • 当结束时间相同时，按照开始时间降序排序 (也就是当结束时间相同时选择开始时间最晚的)
• 2.选择第一个最早结束的会议，用变量last记录时间
• 3.再循环判断剩下的，当 i 的开始时间大于last时，说明是不冲突的可以的，last重新赋值当前的结束时间，计数器加加

#include <iostream>
#include <iomanip>
#include <string.h>
#include <cmath>
#include <algorithm>//算法头文件
#include <fstream>
#include <cstdlib>
#include <vector>
using namespace std;

//盛放会议时间和次数的结构体 
struct Meet{
	int begin_time; //开始的时间 
	int end_time;	//结束的时间 
	int num;	//会议编号 
}meet[100];

bool compare(Meet a, Meet b){
	if(a.end_time == b.end_time){//如果结束时间相等,按照开始时间降序 
		return a.begin_time>b.begin_time;
	}
	return a.begin_time<b.begin_time;//按照开始时间升序(选择最早的时间) 
}

int main(){

	//输入会议总数
	int n;
	cout<<"请输入会议总数："<<endl;
	cin>>n;
	
	//循环输入会议开始和结束的时间
	cout<<"请输入会议的开始时间和结束时间\n";
	for(int i=0; i<n; i++){
		cin>>meet[i].begin_time>>meet[i].end_time;
		meet[i].num = i+1;
	} 
	
	//根据时间排序
	sort(meet, meet+n, compare);
	
	//输出一下排序后的 会议时间表 
	cout<<"编号\t开始时间\t结束时间\n";
	for(int i=0; i<n; i++){
		cout<<meet[i].num<<"\t"<<meet[i].begin_time<<"\t"<<meet[i].end_time<<endl;
	}
	
	int ns = 1;//计数，从一开始是因为第一个会议最早开始肯定符合 
	int last = meet[0].end_time;	//取出第一个的结束时间
	for(int i=1; i<n; i++){
		if(meet[i].begin_time > last){//如果当前的开始时间大于上一个会议的结束时间，说明是可以的 
			ns++;
			last = meet[i].end_time; //取出每一次的结束时间 
		}
	} 
	
	cout<<"最多可以安排"<<ns<<"次会议"<<endl;
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60