Activity Selector Implementations

PADDING = 0
start = [PADDING, 1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12]
finish = [PADDING, 4, 5, 6, 7, 9, 9, 10, 11, 12, 14, 16]
expected_activities = [1, 4, 8, 11]
expect(len(start)).to(equal(len(finish)))

def recursive_activity_selector(start, finish, k: int=0) -> list:
    """Selects the optimal activities

    Note:
     This assumes that the start and finish lists are pre-padded with 
    zeros (1 each).


    Args:
     start: list of start times for each activity
     finish: list of end times for each activity
     k: the current activity (index)

    Returns:
     optimal list of activities
    """
    n = len(start)
    m = k + 1
    while m < n and start[m] < finish[k]:
        m += 1
    if m < n:
        return [m] + recursive_activity_selector(start, finish, m)
    return []

activities = recursive_activity_selector(start, finish)
expect(activities).to(contain_exactly(*expected_activities))
print(activities)

def iterative_activity_selector(start: list, finish: list) -> list:
    """An iterative activity selector

    Note:
     This assumes that the start and finish lists are pre-padded with 
    dummy values.

    Args:
     start: list of starting times
     finish: list of end times
    """
    n = len(start)
    activities = [1]
    k = 1
    for m in range(2, n):
        if start[m] >= finish[k]:
            activities += [m]
            k = m
    return activities

activities = iterative_activity_selector(start, finish)
expect(activities).to(contain_exactly(*expected_activities))
print(activities)