基础算法-贪心算法:会议安排c++
时间: 2023-08-26 20:11:37 浏览: 81
以下是使用C++实现会议安排问题的贪心算法示例代码:
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
// 定义会议结构体
struct Meeting {
int start;
int end;
};
// 比较函数,按照会议结束时间升序排序
bool compare(Meeting m1, Meeting m2) {
return m1.end < m2.end;
}
// 贪心算法实现会议安排
std::vector<Meeting> scheduleMeetings(std::vector<Meeting>& meetings) {
// 按照结束时间排序会议
std::sort(meetings.begin(), meetings.end(), compare);
std::vector<Meeting> schedule; // 会议安排列表
schedule.push_back(meetings[0]); // 将第一个会议加入安排列表
for (int i = 1; i < meetings.size(); i++) {
// 如果当前会议与已安排的最后一个会议不冲突,则将该会议加入安排列表
if (meetings[i].start >= schedule.back().end) {
schedule.push_back(meetings[i]);
}
}
return schedule;
}
int main() {
std::vector<Meeting> meetings = {{1, 3}, {2, 4}, {3, 6}, {5, 7}, {8, 9}, {9, 10}};
std::vector<Meeting> schedule = scheduleMeetings(meetings);
// 输出会议安排
for (int i = 0; i < schedule.size(); i++) {
std::cout << "Meeting " << i+1 << ": " << schedule[i].start << "-" << schedule[i].end << std::endl;
}
return 0;
}
```
以上代码使用了结构体 `Meeting` 来表示一个会议,其中包含开始时间和结束时间。首先,通过定义一个比较函数 `compare` 来按照会议结束时间进行排序。然后,通过 `scheduleMeetings` 函数来实现会议安排的贪心算法。最后,在 `main` 函数中调用 `scheduleMeetings` 函数并输出会议安排结果。
运行以上代码,会输出以下结果:
```
Meeting 1: 1-3
Meeting 2: 5-7
Meeting 3: 8-9
```
这表示在给定的会议列表中,按照贪心算法安排的会议有三个:第一个会议从1到3,第二个会议从5到7,第三个会议从8到9。这些会议之间不存在时间冲突,并且结束时间最早。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)