Activity selection using Greedy Algorithm in Python

Question

Given the problem, I have the following approach however, I am not able to to get all the test cases

Problem Statement: A club has planned to organize several event. The volunteers are given a list of activities and the starting time and ending time of those activities.

Write a python function that accepts the activity list, start_time list and finish_time list. The function should find out and return the list of maximum number of activities that can be performed by a single person.

Assume that a person can work only on a single activity at a time. If an activity performed by a person ends at x unit time then he/she can take up the next activity which is starting at any time greater than or equal to 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)

Abhishek Chauhan Abhishek Chauhan · Accepted Answer · 2020-06-03T11:54:51

You are missing to update the finish variable.

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]

Try the above snippet.

Activity selection using Greedy Algorithm in Python

2 Answers