本文共 1078 字，大约阅读时间需要 3 分钟。

贪心算法之活动选择问题

今天来说说贪心算法之活动选择问题，这是我们讲的贪心算法的第四个例题，有兴趣的读者可以看看前面的几个例题:

1. 题目

    假设有n个活动，这些活动要占用同一片场地，而场地在某时刻只能供一个活动使用。每个活动都有一个开始时间$s_i$和结束时间$f_i$ (题目中时间以整数表示)，表示活动在[$s_i$, $f_i$)区间占用场地。问:安排哪些活动能够使该场地举办的活动的个数最多?

2. 思路

贪心思路:最先结束的活动一定是最优解的一部分。

1. 先假设有一个最优解区域，先放了一些解，我们暂时称这些解为最优解
2. 假设a是所有活动中最先结束的活动，b是最优解中最先结束的活动。
3. 如果a=b,结论成立。
4. 如果a≠b，则b的结束时间一定晚于a的结束时间，则此时用a替换掉最优解中的b, a一定不与最优解中的其他活动时间重叠，因此替换后的解也是最优解。

3. 代码

'''TOPIC: 用贪心算法解决活动选择的问题author: Bluetime: 2020-08-18QQ: 2458682080'''# 思想: 按结束时间最早的进行排序，因为结束时间越早，说明留给后面的活动的时间就越多。# 贪心——贪的就是留给后面的活动的时间越多越好activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]# 保证活动是按结束时间排好序的activities.sort(key=lambda x: x[1])def activity_selection(a):    # 排好序后的a中，活动a[0]一定结束得最早，所以结果中一定有a[0]    res = [a[0]]    for i in range(1, len(a)):        # 如果当前活动的开始时间<=最后一个入选活动的结束时间        if a[i][0] >= res[-1][1]:            res.append(a[i])    return resprint(activity_selection(activities))

结果为:

[(1, 4), (5, 7), (8, 11), (12, 16)]

4. 贪心算法总结

四个例题都是优化问题，最多、最少、最好…但是并不是所有最优化的问题都可以用贪心算法解，比如我们背包问题的0-1问题

转载地址：http://ebiwi.baihongyu.com/