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

贪心算法（Greedy Algorithm）是一种常用的算法思想，用于在求解最优化问题时进行决策。贪心算法每次都选择当前状态下的最优解，而不考虑对后续状态的影响。

在活动安排问题中，我们需要选择一系列互不冲突的活动，使得能够安排尽可能多的活动。假设我们有n个活动，每个活动都有一个开始时间和结束时间。我们需要选择一些活动，使得它们互不冲突，并且能够安排尽可能多的活动。

以下是贪心算法解决活动安排问题的步骤：

1. 将所有活动按照结束时间从早到晚进行排序。
2. 选择第一个活动作为安排的第一个活动。
3. 从第二个活动开始，依次判断当前活动与已经安排的最后一个活动是否互不冲突。如果互不冲突，则将该活动加入安排中。
4. 重复步骤3，直到遍历完所有活动。

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 activitySelection(Activity activities[], int n) {
    qsort(activities, n, sizeof(Activity), compare);

    int i = 0;
    printf("Selected activities: %d ", i);

    for (int j = 1; j < n; j++) {
        if (activities[j].start >= activities[i].end) {
            printf("%d ", j);
            i = j;
        }
    }
}

int main() {
    Activity activities[] = {{1, 3}, {2, 5}, {4, 7}, {6, 9}, {8, 10}, {9, 12}};
    int n = sizeof(activities) / sizeof(activities);

    activitySelection(activities, n);

    return 0;
}

上述代码中，我们使用结构体`Activity`来表示每个活动的开始时间和结束时间。`compare`函数用于排序活动数组，将其按照结束时间从早到晚进行排序。`activitySelection`函数实现了贪心算法的具体逻辑，遍历排序后的活动数组，选择互不冲突的活动并输出其索引。