Lecture "Greedy algorithms", exercise 2

[essepuntato]

Suppose one has to address the maximum number of activities in a day choosing them from a set of available activities, considering that one cannot address more than one activity simultaneously. Each activity is defined by a tuple, where the first element defines the starting time (a value from 0 to 24, indicating the starting hour) while the second element defines the finish time (a value from 0 to 24, indicating the finish hour). Develop the Python function def select_activities(set_of_activities) by using a greedy approach. It takes in input a set of activities of a day and returns the list of the maximum number of non-overlapping activities one can address, ordered according to the starting time. Hint: think about the finish time of each activity and see how it may affect the selection. Accompany the implementation of the function with the appropriate test cases.

[diegochillo]

def select_activities(set_of_activities):
    activities=list(set_of_activities)
    activities.sort()
    activities=list(enumerate(activities))
    lastend=0
    for index, activity in activities:
        if activity[0]<activity[1]:
            if activity[0]<lastend:
                activities[index]=(index,"DEL")
            else:
                lastend=activity[1]
        else:
            activities[index] = (index, "DEL")

    result=[activity for index, activity in activities if activity!='DEL']
    return result

def test_select_activities(set_of_activities, expected):
    result=select_activities(set_of_activities)
    return result==expected

# TEST CASES:

activities={(6, 8), (7, 9), (9, 13), (14, 18), (15, 17), (18, 20), (20, 24), (21, 23), (20, 23), (23,24)}
expected=[(6, 8), (9, 13), (14, 18), (18, 20), (20, 23), (23, 24)]
print (test_select_activities(activities, expected))

activities={(1, 4), (3, 5), (4, 6), (6, 9), (9, 12), (11, 13), (16, 18), (17, 19), (18, 22), (21,24)}
expected=[(1, 4), (4, 6), (6, 9), (9, 12), (16, 18), (18, 22)]
print (test_select_activities(activities, expected))

activities={(22, 24), (7, 9), (16, 20), (16, 22), (13, 17), (11, 14), (20, 22)}
expected=[(7, 9), (11, 14), (16, 20), (20, 22), (22, 24)]
print (test_select_activities(activities, expected))

activities={(24, 22), (7, 9), (16, 20), (16, 22), (13, 17), (11, 14), (20, 22)}
expected=[(7, 9), (11, 14), (16, 20), (20, 22)]
print (test_select_activities(activities, expected))