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 handle more than one activity simultaneously. A tuple defines each activity. The first element specifies the starting time (a value from 0 to 24, indicating the starting hour). The second element represents the finish time (a value from 0 to 24, marking the ending hour). Develop the Python function def select_activities(set_of_activities) 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.

[tommasobattisti]

I've tried to solve the problem by using two functions, one of which is a recursive one. However, I don't know if this approach still permits us to define the algorithm as greedy.

def testAct(set_of_activities, expected):
    result = select_activities(set_of_activities)
    if result == expected:
        return True
    else:
        return False

def select_activities(set_of_activities):
    result =[]
    x = (0, 24)
    while len(result) < 1:
        for act in set_of_activities:
            if act[1] < x[1]:
                x = act                        
        result.append(x)
        set_of_activities.remove(x)
    if len(result) == 1:
        result, set_of_activities = addAct(result, set_of_activities)
    return result

def addAct(res, set):
    y = 0
    for tup in set:
        if tup[0] >= y:
            y = tup[0]
    if y < res[-1][1]:
        return res, set #BASE CASE
    else:
        lis = []
        for el in set:
            if el[0] >= res[-1][1]:
                lis.append(el)
        x = (0, 24)
        for act in lis:
            if act[1] <= x[1]:
                x = act
        res.append(x)
        set.remove(x)
        return addAct(res, set)

activities1 = set([(2, 4), (0, 6), (1,5), (4,8), (4,6), (8, 11), (13,16), (14, 16), (15, 17), (15, 21), (18, 22), (18, 20), (20, 24), (21,22), (22, 23)])
activities2 = set([(0,2), (1,3), (4,8), (3,9), (12,17), (11,12), (13, 15), (17, 20), (18,19), (20, 21), (19,20), (22,24)])

print(testAct(activities1, [(2, 4), (4, 6), (8, 11), (14, 16), (18, 20), (21, 22), (22, 23)]))
print(testAct(activities2, [(0, 2), (4, 8), (11, 12), (13, 15), (18, 19), (19, 20), (20, 21), (22, 24)]))

[Postitisnt]

I'm pretty sure that this solution is not the best one, in particular seen the fact that is really slow... Please check the commented code and answer to my question. Thank you :D

#Function
def select_activities(set_of_activities):
    if len(set_of_activities) == 0:
        print("You have nothing to do...")
        return None

    result = list()
    listTup = list()
    ind = 0
    #ordering elements of the set
    while ind < len(set_of_activities):
        x = set_of_activities.pop()
        listTup.append(x)
    orderedTup = sorted(listTup, key = lambda tup:tup[1])

    #looked for it, someone wrote that the sorted function needs parameters like 
    #"key = lambda tup:tup[1]", in particular when I try to sort a list of tuples.
    #I've seen that without such parameters the output miss one tuple that should be
    #in the solution, but the meaning of key = lambda (...) is not so clear to me...

    temp = (0,24)
    hours = 0
    i = 0

    while i < len(orderedTup) or hours < 24:

    #check for the first element of the solution:
        if len(result) == 0:
            for el in orderedTup:
                if el[1] < temp[1]:
                    temp = el
            duration = temp[1] - temp[0]
            hours += duration
            result.append(temp)

        #check iteratively for the following element of the solution after the last one inserted in 
        #the result list
        for item in orderedTup:
            if item[0] < temp[1]:
                continue
            elif item == temp:
                continue
            else:
                result.append(item)
                break
        temp = result[-1]
        duration = temp[1] - temp[0]
        hours += duration
        i += len(result)

    return result

#Test
def testActivities(set_of_activities, expected):
    listOfAct = select_activities(set_of_activities)
    if listOfAct == expected:
        return True
    else:
        return False

acti = set([(0, 6), (2, 4), (1,5), (4,8), (4,6), (8, 11), (13,16), (14, 16), (15, 17), (15, 21), (18, 22), (18, 20), (20, 24), (21,22), (23, 24)])
acti1 = set([(0,6)])
acti2 = set()
print(testActivities(acti, [(2, 4), (4, 6), (8, 11), (13, 16), (18, 20), (21, 22), (23, 24)]))
print(testActivities(acti1, [(0,6)]))
print(testActivities(acti2, None))