Secuencia de tareas

📖

Este algoritmo resuelve el siguiente problema:

Dado un número

n

de tareas las cuales tienen una fecha límite para ser completadas, teniendo en cuenta que todas las tares se finalizan en una unidad de tiempo, organiza la tareas de tal forma que nos de tiempo a realizar todas las posibles maximizando el beneficio obtenido de las tares elejidas

💡

Este problema es muy similar al problema de selección de actividades, pero un poco más simple ya que en este caso las actividades solo toman una unidad de tiempo.

ℹ️

Descripción del algoritmo

Ordenar las tareas según el beneficio que proporcionan

Situar cada tarea el día más cercano a su fecha límite posible

🧠 Complejidad → $O(n^2)$

###############################################
# Tasks deadline greedy algorithm (iterative) #
###############################################


def deadline_algorithm(tasks, max_time):
    """
    Greedy deadlines algorithm

    - tasks: Array of tuples containing a deadline, a profit and (optionally) an identifier. Format: [deadline, profit, "ID"]
    """

    tasks.sort(key=lambda x: x[1], reverse=True)                        # Sort the tasks by their profit

    time_units = [None] * max_time                                      # Generate the "schedule" array

    # Greedy loop
    while tasks and not all(time_units):                                # Iterate until there are no more tasks left, or until our schedule is full
        task = tasks.pop(0)                                             # Extract the first task (maximum profit)
        deadline = task[0]                                              # Get the deadline of the task
        while time_units[deadline] is not None and deadline >= 0:       # Try to fit the task in the latest deadline possible
            deadline -= 1                                               # If the deadline was taken, try the previous slot

        if deadline > 0:                                                # If the previous loop stopped due to the task can be fitted in the schedule
            time_units[deadline] = task[2]                              # Add the task to the schedule

    return time_units


if __name__ == "__main__":
    tasks = [(1, 100, "A"), (0, 19, "B"), (1, 27, "C"), (0, 25, "D"), (2, 29, "E")]
    solution = deadline_algorithm(tasks, 3)
    print(solution)