2. 贪心法求活动选择问题 【问题描述】 设S ={1, 2, … , n}为活动的集合, si, fi 分别为活动 i 的开始和结束时间， i =1, 2, … , n. 定义：活动 i 与 j 相容 Û si ³ fj 或 sj ³ fi . 求：最大的两两相容的活动集 A. 【输入形式】活动个数n，第i个活动的序号i、开始时间及结束时间。 【输出形式】符合要求的活动顺序 【样例输入】 10 1 2 6 2 3 5 3 1 4 4 5 7 5 4 9 6 5 9 7 6 10 8 8 11 9 8 12 10 2 13 【样例输出】

实现贪心算法求解活动选择问题的思路如下：

1. 将所有活动按照结束时间从早到晚排序，结束时间相同的活动按照开始时间从早到晚排序。

2. 选择第一个活动，即结束时间最早的活动，加入集合A中。

3. 从剩余的活动中选择一个开始时间晚于活动A的结束时间的活动，加入集合A中。

4. 重复步骤3，直到所有活动都被考虑完。

下面是Python代码实现：

n = int(input())
activities = []
for i in range(n):
    index, start, end = map(int, input().split())
    activities.append((index, start, end))

# 按照结束时间从早到晚排序，结束时间相同的活动按照开始时间从早到晚排序
activities.sort(key=lambda x: (x[2], x[1]))

# 选择第一个活动
selected = [activities[0]]

# 从剩余的活动中选择符合条件的活动
for i in range(1, n):
    if activities[i][1] >= selected[-1][2]:
        selected.append(activities[i])

# 输出结果
for activity in selected:
    print(activity[0], end=' ')

对于样例输入，程序输出的结果为：

3 5 8 10 

相关问题

输入：S={1, 2, …, n}, F={ [si，fi] }，ni1 输出：S中的最大相容活动集合

这是一个经典的贪心算法问题，通常被称为“活动选择问题”。

首先，将所有的活动按照结束时间从早到晚排序。然后选择第一个活动放入最大相容活动集合中。接着，依次考虑每一个活动，如果当前活动的开始时间晚于上一个活动的结束时间，则将该活动放入最大相容活动集合中。

具体实现可以使用以下伪代码：

ActivitySelection(S, F):
    n = S.length
    A = {1}
    j = 1
    for i from 2 to n:
        if S[i] >= F[j]:
            A = A U {i}
            j = i
    return A

其中，S 和 F 分别是开始时间和结束时间的数组，A 是最大相容活动集合，j 记录上一个活动的结束时间。

该算法的时间复杂度为 O(nlogn)，主要由排序操作决定。

贪心算法活动安排问题c语言实现以及数学模型的建立存储结构选择

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

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

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

// 比较函数，按结束时间升序排列
int cmp(const void *a, const void *b) {
    return ((Activity*)a)->end - ((Activity*)b)->end;
}

// 贪心算法
int activitySelection(Activity *activities, int n) {
    int count = 1;  // 计数器，记录已安排的活动数
    int end = activities[0].end;  // 记录上一个已安排活动的结束时间
    for (int i = 1; i < n; i++) {
        if (activities[i].start >= end) {
            count++;
            end = activities[i].end;
        }
    }
    return count;
}

int main() {
    int n;
    printf("请输入活动数：");
    scanf("%d", &n);

    Activity *activities = (Activity*)malloc(n * sizeof(Activity));
    printf("请按开始时间和结束时间的顺序依次输入每个活动的时间：\n");
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &activities[i].start, &activities[i].end);
    }

    qsort(activities, n, sizeof(Activity), cmp);  // 按结束时间升序排列

    printf("最多可以安排%d个活动\n", activitySelection(activities, n));
    free(activities);
    return 0;
}

该实现中，我们使用了结构体来存储活动的开始时间和结束时间，使用了qsort函数来按结束时间升序排列，使用了activitySelection函数来实现贪心算法的核心逻辑。

对于数学模型的建立，我们可以将活动安排问题看作是一个集合覆盖问题，其中每个活动代表一个集合，集合中包含的元素是活动的时间段，我们需要选择尽可能少的集合，使得它们的并集覆盖了所有的元素。因此，我们可以使用一个数组来存储活动的开始时间和结束时间，使用一个二维数组来表示集合与元素之间的关系，例如：

int sets[MAX_SETS][MAX_ELEMENTS];  // 集合与元素之间的关系

其中，MAX_SETS表示最大集合数，MAX_ELEMENTS表示每个集合中最多包含的元素数。对于每个活动i，我们可以将其时间段表示为一个集合Si，其中元素j表示时间段中的第j个时间点，例如：

for (int i = 0; i < n; i++) {
    for (int j = activities[i].start; j <= activities[i].end; j++) {
        sets[i][j] = 1;  // 时间点j属于集合Si
    }
}

然后，我们可以使用贪心算法来选择最少的集合，使得它们的并集覆盖了所有的元素，例如：

int selected[MAX_SETS] = {0};  // 记录已经选择的集合
int count = 0;  // 记录已经选择的集合数
for (int j = 0; j < MAX_ELEMENTS; j++) {
    int max_cover = 0;  // 记录当前元素被最多集合覆盖的次数
    int max_set = -1;   // 记录覆盖当前元素最多的集合
    for (int i = 0; i < MAX_SETS; i++) {
        if (!selected[i] && sets[i][j] && cover[i] > max_cover) {
            max_cover = cover[i];
            max_set = i;
        }
    }
    if (max_set != -1) {
        selected[max_set] = 1;
        count++;
        for (int k = 0; k < MAX_ELEMENTS; k++) {
            if (sets[max_set][k]) {
                cover[k]++;
            }
        }
    }
}

其中，selected数组记录已经选择的集合，cover数组记录每个元素被覆盖的次数。该算法的时间复杂度为O(MAX_SETS * MAX_ELEMENTS ^ 2)，其中MAX_SETS表示集合数，MAX_ELEMENTS表示每个集合中最多包含的元素数。