Selección de actividades

📖

Este es tipo de algoritmo voraz que resuelve el siguiente problema: Dada una lista de

n

actividades, cada una con un tiempo de inicio y otro de finalización, determinar cuales son las actividades que debe realizar para maximizar el número de actividades realizadas en total. Los tiempos no se pueden solapar.

ℹ️

Descripción del algoritmo

Ordenar la lista de actividades según el valor del tiempo de finalización

Extraer actividades, cuyo tiempo de inicio sea mayor que el tiempo de finalización de la última actividad extraida

🧠 Complejidad → $O(n·\log n)$

💡

Para este algoritmo ordenaremos según el tiempo de finalización debido a que de esta manera nos aseguraremos que la última actividad escogida termina lo antes posible. Si escogieramos ordenar por el tiempo de inicio, podría ocurrir que si hay una actividad que toma todo el tiempo disponible, el algoritmo siempre escogiera esa actividad y ninguna más

##############################################
# Activities selection algorithm (iterative) #
##############################################


def activities_algorithm(data):
    """
    Activity selection greedy algorithm

    - data: Array of activities. Format: ["name", ini_time, fin_time].
        - The name is not used by the algorithm
    """
    data.sort(key=lambda x: x[1])           # Sort the activities by their finishing time
    sol = []                                # Create the solutions array

    # Greedy algorithm
    last = 0                                # Store the finishing time of the last activity selected
    while data:                             # While there are still activities in the list
        ini, fin = data.pop(0)              # Extract the first activity (array is already sorted)
        if ini >= last:                     # If the activity doesn't overlap with the previous one, add it to the solution
            last = fin                      # Set the activity as the last activity of the solution
            sol.append((ini,fin))           # Add it to the solution array

    return sol


#################################

if __name__ == "__main__":
    n_activities = int(input())
    activities = []

    for _ in range(n_activities):
        name, ini, fin = input().strip().split()
        activities.append((name, int(ini), int(fin)))

    solution = activities_algorithm(activities)
    print(len(solution))