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.

[sntcristian]

def test_select_activities(set_of_activities, expected):
    result = select_activity(set_of_activities)
    if expected == len(result):
        bool_result = True
        for idx, activity in enumerate(result):
            if idx > 0:
                bool_result = bool_result and (activity[0] >= result[idx - 1][1])

        return bool_result
    else:
        return False

def select_activity(set_of_activities):
    start = 0
    end = 24
    result = []
    prev_len = len(result)
    for hour in range(start+1, end+1):
        if len(set_of_activities) == 0:
            return result
        else:
            for activity in set_of_activities:
                if activity[0] >= start and activity[1] <= hour:
                    result.append(activity)
                    start = activity[1]
                    break
            if len(result) > prev_len:
                prev_len = len(result)
                set_of_activities.remove(result[-1])
    return result

activities_1 = set()
activities_1.add((0, 3))
activities_1.add((4, 7))
activities_1.add((2, 12))
activities_1.add((7, 8))
activities_1.add((10, 13))
activities_1.add((12, 20))
activities_1.add((14, 17))
activities_1.add((16, 19))
activities_1.add((17, 24))
activities_1.add((21, 23))

print(test_select_activities(activities_1, 6))
print(test_select_activities(set(), 0))