编写完整C代码:给你一个整数 n ,共有编号从 0 到 n - 1 的 n 个会议室。 给你一个二维整数数组 meetings ,其中 meetings[i] = [starti, endi] 表示一场会议将会在 半闭 时间区间 [starti, endi) 举办。所有 starti 的值 互不相同 。 会议将会按以下方式分配给会议室: 每场会议都会在未占用且编号 最小 的会议室举办。 如果没有可用的会议室,会议将会延期,直到存在空闲的会议室。延期会议的持续时间和原会议持续时间 相同 。 当会议室处于未占用状态时,将会优先提供给原 开始 时间更早的会议。 返回举办最多次会议的房间 编号 。如果存在多个房间满足此条件,则返回编号 最小 的房间。 半闭区间 [a, b) 是 a 和 b 之间的区间,包括 a 但 不包括 b 。
时间: 2024-02-27 09:57:55 浏览: 121
以下是完整的 C 代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 1000
int cmp(const void *a, const void *b) {
int *a1 = *(int **)a;
int *b1 = *(int **)b;
if (a1[0] == b1[0]) {
return a1[1] - b1[1];
}
return a1[0] - b1[0];
}
int minMeetingRooms(int** meetings, int meetingsSize, int* meetingsColSize) {
int i, j, k, min_idx, max_rooms = 1, cur_rooms;
int **meeting_starts = (int **)malloc(sizeof(int *) * meetingsSize);
for (i = 0; i < meetingsSize; i++) {
meeting_starts[i] = (int *)malloc(sizeof(int) * 2);
meeting_starts[i][0] = meetings[i][0];
meeting_starts[i][1] = meetings[i][1];
}
qsort(meeting_starts, meetingsSize, sizeof(int *), cmp);
int end_times[MAX_N] = {0};
for (i = 0; i < meetingsSize; i++) {
min_idx = -1;
for (j = 0; j < max_rooms; j++) {
if (end_times[j] <= meeting_starts[i][0]) {
if (min_idx == -1 || end_times[j] < end_times[min_idx]) {
min_idx = j;
}
}
}
if (min_idx == -1) {
end_times[max_rooms++] = meeting_starts[i][1];
} else {
end_times[min_idx] = meeting_starts[i][1];
}
}
return max_rooms;
}
int main() {
int meetings[MAX_N][2];
int n, i;
printf("请输入会议室数量:");
scanf("%d", &n);
printf("请输入每个会议的开始时间和结束时间:\n");
for (i = 0; i < n; i++) {
scanf("%d %d", &meetings[i][0], &meetings[i][1]);
}
int rooms = minMeetingRooms((int **)meetings, n, NULL);
printf("最多可以举办 %d 场会议\n", rooms);
return 0;
}
```
该代码使用了贪心算法,首先将所有会议按照开始时间从小到大排序,然后遍历会议数组,对于每个会议,找到可用的会议室中结束时间最早的那个,如果找不到可用的会议室,就增加一个新的会议室。最后返回使用的最大会议室数量即可。
阅读全文