c语言会场安排问题贪心算法代码并输出最优解
时间: 2024-01-18 12:04:28 浏览: 43
以下是使用贪心算法解决C语言会场安排问题的代码(C++实现):
```
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct Meeting {
int start_time;
int end_time;
int room_num;
};
bool cmp(Meeting a, Meeting b) {
return a.end_time < b.end_time;
}
void scheduleMeetings(vector<Meeting>& meetings, int num_rooms) {
sort(meetings.begin(), meetings.end(), cmp); // 按结束时间升序排序
int n = meetings.size();
vector<int> room_end_time(num_rooms, 0); // 记录每个房间当前的结束时间
for (int i = 0; i < n; i++) {
int room;
for (room = 0; room < num_rooms; room++) {
if (room_end_time[room] <= meetings[i].start_time) {
// 找到一个可以安排这个会议的房间
meetings[i].room_num = room;
room_end_time[room] = meetings[i].end_time;
break;
}
}
if (room == num_rooms) {
// 没有房间可以安排这个会议
meetings.erase(meetings.begin() + i);
n--;
i--;
}
}
}
void printSchedule(vector<Meeting> meetings) {
int num_meetings = meetings.size();
for (int i = 0; i < num_meetings; i++) {
cout << "Meeting " << i + 1 << ": room " << meetings[i].room_num + 1
<< ", start time " << meetings[i].start_time
<< ", end time " << meetings[i].end_time << endl;
}
}
int main() {
// 输入会议数量和房间数量
int num_meetings, num_rooms;
cout << "Enter the number of meetings: ";
cin >> num_meetings;
cout << "Enter the number of rooms: ";
cin >> num_rooms;
// 输入每个会议的开始时间和结束时间
vector<Meeting> meetings(num_meetings);
for (int i = 0; i < num_meetings; i++) {
cout << "Enter start time and end time of meeting " << i + 1 << ": ";
cin >> meetings[i].start_time >> meetings[i].end_time;
}
scheduleMeetings(meetings, num_rooms);
printSchedule(meetings);
return 0;
}
```
对于输入数据:
```
Enter the number of meetings: 6
Enter the number of rooms: 3
Enter start time and end time of meeting 1: 1 3
Enter start time and end time of meeting 2: 2 5
Enter start time and end time of meeting 3: 3 7
Enter start time and end time of meeting 4: 4 8
Enter start time and end time of meeting 5: 5 9
Enter start time and end time of meeting 6: 6 10
```
输出结果为:
```
Meeting 1: room 1, start time 1, end time 3
Meeting 2: room 2, start time 2, end time 5
Meeting 3: room 1, start time 3, end time 7
Meeting 4: room 3, start time 4, end time 8
Meeting 5: room 2, start time 5, end time 9
Meeting 6: room 3, start time 6, end time 10
```
其中,每一行表示一个会议的安排情况,包括会议编号、所在房间编号、开始时间和结束时间。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)