Activity 在 Python 中使用贪心算法进行选择

Question

鉴于这个问题，我有以下方法，但是我无法获得所有测试用例

问题陈述：某俱乐部计划举办多项活动。向志愿者提供活动列表以及这些活动的开始时间和结束时间。

编写一个 python 函数，接受 activity 列表、start_time 列表和 finish_time 列表。该函数应找出并 return 一个人可以执行的最大活动数列表。

假设一个人一次只能处理一个 activity。如果一个人执行的 activity 在 x 单位时间结束，那么 he/she 可以占用下一个 activity，它在大于或等于 x+1 的任何时间开始。

def find_maximum_activities(activity_list,start_time_list, finish_time_list):
    activities = list(zip(activity_list, start_time_list, finish_time_list))
    activities.sort(key = lambda x: x[2])
    finish = 0
    result = []
    for i in activities:
        if finish <= i[1]:
            result.append(i[0])
            finish = i[2]
    return result
    
activity_list=[1,2,3,4,5,6,7]
start_time_list=[1,4,2,3,6,8,6]
finish_time_list=[2,6,4,5,7,10,9]


result=find_maximum_activities(activity_list,start_time_list, finish_time_list)
print("The maximum set of activities that can be completed:",result)

Answer 1

您缺少更新完成变量。

activities.sort(key=lambda x: x[1])
finish = -1
result = []

for i in activities:
    if finish <= i[0]:
        result.append(d[i])
        finish = i[1]

试试上面的代码片段。

Answer 2

我不认为这是一个贪婪的问题。

IMO，这是一个DP问题。

给定一个 Activity，您应该已经计算了此 activity 之后开始的每个 activity 的答案。

因此按开始时间的降序处理活动。

因此给定 activity 的答案将是 1 + max(Answer for all activity that start after this ends)。

使max(Answer for all activity that start after this ends)成为O(1) | O(log(n))操作。

Activity 在 Python 中使用贪心算法进行选择

Activity selection using Greedy Algorithm in Python

python

algorithm

greedy