Job Sequencing Problem

Q: ¿Cuál es la complejidad temporal del problema de secuenciación de trabajos?

Con un conjunto disjunto, el tiempo es O(n log n) , dominado por la ordenación, y el espacio es O(n) . Buscar hacia atrás desde cada fecha límite hasta encontrar un espacio libre cuesta O(n²) cuando la mayoría de las fechas límite son grandes.

MedioVoraz Ordenación

+10

Recibes n trabajos como dos arreglos: el trabajo i genera profit[i] si termina antes o en el instante deadline[i]. Cada trabajo dura una unidad de tiempo, ejecutas un trabajo a la vez empezando en el instante 0 y puedes omitir cualquier trabajo. Un trabajo con fecha límite 2 puede ejecutarse de 0 a 1 o de 1 a 2.

Devuelve el mayor beneficio total que puedes obtener.

Función

jobSequencing(deadline: integer-array, profit: integer-array) → integer

deadlineinteger-array: el momento en que debe terminarse cada tarea, de 1 a n
profitinteger-array: lo que gana cada trabajo; profit[i] corresponde a deadline[i]
Devuelveinteger: el mayor beneficio total de los trabajos que pueden terminar todos antes de sus fechas límite

Restricciones

1 ≤ deadline.length == profit.length ≤ 5000
1 ≤ deadline[i] ≤ n, donde n es el número de trabajos
1 ≤ profit[i] ≤ 10⁵
Los arreglos no están ordenados. Varios trabajos pueden compartir una fecha límite o una ganancia.

Ejemplos

Entrada: deadline = [3, 1, 2, 3, 1]profit = [40, 35, 30, 25, 50]
Salida: 120
Explicación: Solo cabe uno de los dos trabajos con plazo límite 1, así que ejecuta el que vale 50. El trabajo que vale 30 termina después en su plazo límite 2 y el trabajo que vale 40 en su plazo límite 3: 50 + 30 + 40 = 120.

Entrada: deadline = [1, 1, 1]profit = [5, 9, 7]
Salida: 9
Explicación: Los tres trabajos deben terminar antes del tiempo 1, y solo cabe un trabajo antes de ese momento. El mejor de ellos gana 9.

Para ir más allá

¿Y si el trabajo i tarda duration[i] unidades de tiempo en lugar de una? ¿Sigue dando el mejor total tomar primero el trabajo más rentable?

Solución

Tú eliges qué trabajos conservar y cuándo ejecutarlos. Una regla voraz resuelve ambas cosas: toma los trabajos empezando por el más rentable y coloca cada uno en el último intervalo libre en su fecha límite o antes; omítelo si no hay ninguno libre. Un conjunto disjunto encuentra ese intervalo sin recorrer los que ya están ocupados.

Selección voraz por beneficio, buscando un espacio libre

Intuición

Divide el tiempo en intervalos: el intervalo t va de t-1 a t, un trabajo con fecha límite d puede usar los intervalos del 1 al d, y ninguna fecha límite supera n. Elegir primero el trabajo más rentable es seguro: si todos los intervalos que podría usar están ocupados, intercambiarlo por el trabajo de uno de ellos produce al menos la misma ganancia. Reservar el intervalo más tardío es seguro porque los intervalos iniciales son los únicos que pueden usar los trabajos con fechas límite cercanas.

El costo está en el recorrido. Cuando todas las fechas límite son n, el trabajo número k pasa por los k-1 intervalos ocupados: aproximadamente n²/2, o 12.5 millones de pasos cuando n = 5000.

Algoritmo

Ordena los trabajos por beneficio, de mayor a menor, manteniendo cada fecha límite junto con su beneficio.
Crea un arreglo taken de n + 1 indicadores, todos en false.
Para cada trabajo, recorre t hacia abajo desde su fecha límite hasta 1 y detente en el primer espacio que no esté ocupado.
Si encontraste uno, márcalo como ocupado y suma el beneficio del trabajo a total.
Devuelve total.

def jobSequencing(deadline, profit):
    n = len(deadline)
    taken = [False] * (n + 1)  # taken[t]: the time unit from t-1 to t is booked
    total = 0
    for i in sorted(range(n), key=lambda i: profit[i], reverse=True):  # most profitable first
        for t in range(deadline[i], 0, -1):  # latest free slot first
            if not taken[t]:
                taken[t] = True
                total += profit[i]
                break
    return total

Codicioso por beneficio con un conjunto disjunto de espacios libres

Intuición

El recorrido vuelve una y otra vez sobre los mismos intervalos ocupados. Una estructura de conjuntos disjuntos sobre los intervalos de 0 a n los omite: parent[t] = t mientras el intervalo t esté libre, y reservarlo establece parent[t] = t-1, así que seguir los punteros desde una fecha límite lleva al intervalo libre más reciente. Llegar al intervalo 0 significa que no queda ninguno. La compresión de caminos por mitades apunta cada intervalo que recorres dos pasos adelante, por lo que los recorridos posteriores son más cortos.

En el tercer ejemplo, los trabajos que valen 60 y 50 reservan los intervalos 2 y 1. El trabajo que vale 20, con fecha límite 2, sigue el recorrido de 2 a 1 y luego a 0, y se omite.

La ordenación cuesta O(n log n), y con la compresión de caminos por mitades cada consulta cuesta O(log n) amortizado, así que el total sigue siendo O(n log n).

Algoritmo

Ordena los trabajos por beneficio, de mayor a menor, manteniendo cada fecha límite junto a su beneficio.
Establece parent[t] = t para cada espacio t desde 0 hasta n.
Para cada trabajo, empieza en slot = deadline y sigue parent hasta que parent[slot] == slot, reduciendo a la mitad el camino mientras avanzas.
Si slot > 0, suma el beneficio del trabajo y establece parent[slot] = slot-1; de lo contrario, omite el trabajo.
Devuelve el total.

def jobSequencing(deadline, profit):
    n = len(deadline)
    # following parent from slot t ends at the latest free slot at or before t; 0 means none is left
    parent = list(range(n + 1))
    total = 0
    for i in sorted(range(n), key=lambda i: profit[i], reverse=True):  # most profitable first
        slot = deadline[i]
        while parent[slot] != slot:
            parent[slot] = parent[parent[slot]]  # halve the path as you go
            slot = parent[slot]
        if slot > 0:
            total += profit[i]
            parent[slot] = slot - 1  # booked: its chain continues at the slot before it
    return total

Errores comunes y casos límite

Colocar un trabajo en la primera ranura libre. En el tercer ejemplo, el trabajo que vale 60 ocuparía la ranura 1 y se perdería el trabajo que vale 50: 80 en lugar de 110.
Tomar los trabajos en orden de fecha límite. Con las fechas límite [1, 1] y las ganancias [1, 100], el trabajo barato ocupa la única ranura y ganas 1 en lugar de 100.
Dimensionar el arreglo de ranuras como n en lugar de n + 1. Una fecha límite igual a n entonces intenta leer más allá del final.
Ordenar las ganancias por separado. Cada fecha límite tiene que moverse junto con su ganancia.
Escribir el paso de búsqueda con recursión. Una cadena que pase por miles de ranuras ocupadas puede desbordar la pila; usa un bucle.

Preguntas frecuentes3

¿Cuál es la complejidad temporal del problema de secuenciación de trabajos?

Con un conjunto disjunto, el tiempo es O(n log n), dominado por la ordenación, y el espacio es O(n). Buscar hacia atrás desde cada fecha límite hasta encontrar un espacio libre cuesta O(n²) cuando la mayoría de las fechas límite son grandes.

¿Por qué funciona el enfoque voraz para la secuenciación de trabajos?

Alguna planificación óptima contiene el trabajo más rentable. Si se deja fuera y hay un espacio libre antes de su fecha límite, añadirlo genera más ganancias; si todos esos espacios están ocupados, reemplazar un trabajo por este genera al menos las mismas ganancias. El argumento se repite con los trabajos restantes.

¿Se puede resolver la secuenciación de trabajos usando un heap?

Sí. Ordena los trabajos por fecha límite e inserta cada ganancia en un montículo mínimo. Siempre que el montículo contenga más trabajos de los que permite la fecha límite actual, extrae la ganancia más pequeña. Al final, el montículo contiene el mejor conjunto de trabajos, y su suma es la respuesta, en O(n log n).

def jobSequencing(deadline, profit):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumentos

deadline = [3, 1, 2, 3, 1]
profit = [40, 35, 30, 25, 50]

Salida Esperada