贪心算法活动安排问题代码

下面是一个简单的贪心算法活动安排问题的 Python 代码实现：

def activity_selection(start, end):
    n = len(end)
    activities = []
    i = 0
    for j in range(n):
        if start[j] >= end[i]:
            activities.append(j)
            i = j
    return activities

# 测试
start = [1, 3, 0, 5, 8, 5]
end = [2, 4, 6, 7, 9, 9]
result = activity_selection(start, end)
print(result)  # 输出 [0, 1, 3, 4]

其中，`start` 和 `end` 分别表示每个活动的开始时间和结束时间。函数 `activity_selection` 返回一个列表，包含选中的活动的索引。

这个贪心算法的思路是：将所有活动按照结束时间从早到晚排序，然后从第一个活动开始，依次选择结束时间最早的活动，直到所有活动都被选中或者没有可选的活动为止。

相关问题

用贪心算法解决活动安排问题代码

在解决活动安排问题（也称为任务调度、课程表冲突等）时，贪心算法通常用于寻找局部最优解，比如选择能够最大程度地覆盖时间窗口的活动。这里是一个简单的Python代码示例，使用贪心策略来尽可能地将活动添加到日程中，同时避免时间冲突：

def activity_scheduling(activities, time_limit):
    activities.sort(key=lambda x: (x[1] - x[0], x[0]))  # 按结束时间降序，开始时间升序排序
    schedule = []
    
    for activity in activities:
        if not schedule or activity[0] >= schedule[-1][1]:  # 如果没有冲突或者新的活动开始时间大于等于上一个活动结束时间
            schedule.append(activity)  # 添加活动到日程
        else:  # 存在冲突，跳过此活动
            pass
            
    return schedule

# 示例：
activities = [(1, 3), (2, 4), (7, 9), (5, 6)]  # 活动开始和结束时间列表
time_limit = 10  # 总的时间限制
result = activity_scheduling(activities, time_limit)
print("Scheduling:", result)

# 

贪心算法活动安排问题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`函数实现了贪心算法的具体逻辑，遍历排序后的活动数组，选择互不冲突的活动并输出其索引。