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

活动安排问题是指在一组互相竞争的活动中选出最大的相容活动集合。贪心算法是解决这个问题的一种有效方法。以下是C语言实现活动安排问题的贪心算法的步骤：

1.将所有活动按照结束时间从早到晚排序。
2.选择第一个活动作为已安排的活动。
3.对于剩余的活动，如果该活动的开始时间晚于或等于已安排的活动的结束时间，则将该活动加入已安排的活动集合中。
4.重复步骤3，直到所有活动都被考虑过。

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

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

// 活动结构体
struct Activity {
    int start;
    int end;
};

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

// 贪心算法求解活动安排问题
void activitySelection(struct Activity activities[], int n) {
    // 按照结束时间从早到晚排序
    qsort(activities, n, sizeof(struct Activity), cmp);

    // 第一个活动一定会被选中
    int i = 0;
    printf("(%d, %d) ", activities[i].start, activities[i].end);

    // 选择其他活动
    for (int j = 1; j < n; j++) {
        if (activities[j].start >= activities[i].end) {
            printf("(%d, %d) ", activities[j].start, activities[j].end);
            i = j;
        }
    }
}

int main() {
    // 测试数据
    struct 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[0]);

    // 求解活动安排问题
    activitySelection(activities, n);

    return 0;
}