贪心算法之活动选择问题

今天来说说贪心算法之活动选择问题，这是我们讲的贪心算法的第四个例题，有兴趣的读者可以看看前面的几个例题:
数据结构(python) —— 【29: 贪心算法之换钱问题】
数据结构(python) —— 【30: 贪心算法之背包问题】
数据结构(python) —— 【31: 贪心算法之数字拼接问题】

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: Blue
time: 2020-08-18
QQ: 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 res
print(activity_selection(activities))

结果为:

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

4. 贪心算法总结

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