活动安排问题贪心算法C语言

贪心算法是一种常用的解决问题的算法思想，它在每一步选择中都采取当前状态下最优的选择，从而希望最终能够得到全局最优解。下面是贪心算法在活动安排问题中的应用和C语言实现：

活动安排问题是指给定一组活动，每个活动都有一个开始时间和结束时间，要求在给定时间内安排尽可能多的互不冲突的活动。

贪心算法在活动安排问题中的思路是，首先按照结束时间对所有活动进行排序，然后依次选择结束时间最早且与前面已选择的活动不冲突的活动。

以下是使用C语言实现活动安排问题的贪心算法代码：

#include <stdio.h>
#include <stdlib.h>

// 活动结构体
typedef struct {
    int start;  // 开始时间
    int end;    // 结束时间
} Activity;

// 比较函数，用于排序
int compare(const void *a, const void *b) {
    return ((Activity*)a)->end - ((Activity*)b)->end;
}

// 贪心算法解决活动安排问题
void activitySchedule(Activity activities[], int n) {
    // 对活动按照结束时间进行排序
    qsort(activities, n, sizeof(Activity), compare);
    
    printf("选择的活动：\n");
    
    // 第一个活动必定会被选择
    printf("(%d, %d)\n", activities.start, activities.end);
    
    int lastEnd = activities.end;
    
    // 从第二个活动开始遍历，选择与前面已选择的活动不冲突的活动
    for (int i = 1; i < n; i++) {
        if (activities[i].start >= lastEnd) {
            printf("(%d, %d)\n", activities[i].start, activities[i].end);
            lastEnd = activities[i].end;
        }
    }
}

int main() {
    // 示例数据
    Activity activities[] = {{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(activities) / sizeof(activities);
    
    activitySchedule(activities, n);
    
    return 0;
}

输出结果为：

选择的活动：
(1, 4)
(5, 7)
(8, 11)
(12, 14)

这些是选取的互不冲突的活动。贪心算法在该问题中得到了最优解。