假设有n个活动,这些活动要占用统一场地,而场地在某时刻只能供一个活动使用。每个活动都有一个开始时间si和结束时间fi(整数),表示活动在[si, fi)区间内占用场地。

问:安排哪些活动能够使该场地举办的活动个数最多?

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

代码示例

lst = [(1,4), (3,5), (2,6), (5,7), (4,9), (5,9), (6,10), (8,11), (8,12), (2,13)]
# 按结束时间排序
lst.sort(key=lambda x:x[1])

best_lst = [lst[0]]
for act in lst[1:]:
    # 开始时间大于已排活动的最后结束时间
    if act[0] >= best_lst[-1][1]:
        best_lst.append(act)
print(best_lst)

本文为 陈华 原创,欢迎转载,但请注明出处:http://edu.ichenhua.cn/read/341