activity greedy problem

act.py

# ACTIVITY PROBLEMS

# given a set of n activities with their start and finish times, 
# we need to select maximum number of non-conflicting activities 
# that can be performed by a single person, 
# given that the person can handle only one activity at a time.

activities = [(1, 3), (3, 4), (2, 5), (0, 7), (5, 9), (8, 10), (11, 12)]


# find overlapping activities
def find_none_overlapping(activities):
    none_overlapping_activities = []
    # we sort the activities based on their finishing times, unlike the starting time
    # that we had to wait for the longest finishing time to be completed
    # thus we couldn't choose other activities due to handling only
    # one at a time and conflicting issues!
    sorted_activities_based_on_fi = sorted(activities, key=lambda acts: acts[1])
    # select the first least finishing time activity as the starting one
    # this intuition let us greedily choosing the maximum activities
    least_act = activities[0]
    for i in range(1, len(activities)):
        # if the starting time of other activity is greater than the 
        # finishing time of the first one we know that we can do that 
        # activity after finishing the first one cause when we finish 
        # the first one the second on will start due to having greater starting time! 
        if activities[i][0] >= least_act[1]:
            none_overlapping_activities.append(activities[i])
    return none_overlapping_activities

print(find_none_overlapping(activities))