贪心算法解决会议安排问题：C语言实现

假设有 11 个会议需要安排，每个会议都有开始时间和结束时间，目标是找出满足目标要求的会议集合，使得在这个集合中，每个会议都能独立进行，且会议数量最多。

问题描述:

设有 11 个会议等待安排，用贪心法找出满足目标要求的会议集合。这些会议按结束时间分别为 {1-4} {3-5} {0-6} {5-7} {3-8} {5-9} {6-10} {8-11} {8-12} {2-13} {12-14}，给出 C 语言代码内容：

#include <stdio.h>
#include <stdbool.h>

// 定义会议的结构体
typedef struct {
    int start;
    int end;
} Meeting;

// 比较函数，用于对会议按结束时间进行排序
int compare(const void* a, const void* b) {
    Meeting* meeting1 = (Meeting*)a;
    Meeting* meeting2 = (Meeting*)b;
    return meeting1->end - meeting2->end;
}

void findOptimalSchedule(Meeting meetings[], int n) {
    // 将会议按结束时间排序
    qsort(meetings, n, sizeof(Meeting), compare);
    
    // 存储最终的会议集合
    Meeting optimalSchedule[n];
    int count = 0;
    
    // 将第一个会议加入到最终的会议集合中
    optimalSchedule[count++] = meetings[0];
    
    // 遍历剩余的会议
    for (int i = 1; i < n; i++) {
        // 如果当前会议的开始时间晚于等于最后一个会议的结束时间，则将其加入到最终的会议集合中
        if (meetings[i].start >= optimalSchedule[count - 1].end) {
            optimalSchedule[count++] = meetings[i];
        }
    }
    
    // 输出最终的会议集合
    printf("最优会议安排为：\n");
    for (int i = 0; i < count; i++) {
        printf("会议%d：开始时间：%d，结束时间：%d\n", i+1, optimalSchedule[i].start, optimalSchedule[i].end);
    }
}

int main() {
    // 定义会议数组
    Meeting meetings[] = {{1, 4}, {3, 5}, {0, 6}, {5, 7}, {3, 8}, {5, 9}, {6, 10}, {8, 11}, {8, 12}, {2, 13}, {12, 14}};
    int n = sizeof(meetings) / sizeof(meetings[0]);
    
    // 调用贪心算法找出最优会议安排
    findOptimalSchedule(meetings, n);
    
    return 0;
}

代码解析:

定义结构体: 使用 Meeting 结构体存储每个会议的开始时间和结束时间。
排序: 使用 qsort 函数根据会议的结束时间进行排序。
贪心算法: 遍历排序后的会议列表，如果当前会议的开始时间晚于等于最后一个已选择会议的结束时间，则将其加入到最终的会议集合中。
输出结果: 输出最终的会议安排。

运行结果:

最优会议安排为：
会议1：开始时间：1，结束时间：4
会议2：开始时间：5，结束时间：7
会议3：开始时间：8，结束时间：11
会议4：开始时间：12，结束时间：14

代码说明:

这段代码使用贪心算法，通过将会议按结束时间排序，并依次判断每个会议是否能加入到最终的会议集合中。这是一种简单有效的算法，能快速找到一个相对较优的会议安排方案，但可能并非全局最优解。

应用场景:

贪心算法常用于解决资源分配、调度、最优路径等问题。在实际应用中，需要根据具体问题和约束条件来选择合适的贪心策略。