Job Sequencing Problem

Q: Qual è la complessità temporale del problema di sequenziamento dei lavori?

Con una struttura di insiemi disgiunti, il tempo è O(n log n) , dominato dall’ordinamento, e lo spazio è O(n) . Scorrere all’indietro a partire da ogni scadenza per trovare uno slot libero richiede O(n²) quando la maggior parte delle scadenze è lontana.

MedioGreedy Ordinamento

+10

Ti vengono assegnati n lavori sotto forma di due array: il lavoro i frutta profit[i] se termina entro il tempo deadline[i]. Ogni lavoro richiede un'unità di tempo, ne esegui uno alla volta a partire dal tempo 0 e puoi saltare qualsiasi lavoro. Un lavoro con scadenza 2 può essere eseguito da 0 a 1 oppure da 1 a 2.

Restituisci il profitto totale massimo che puoi ottenere.

Funzione

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

deadlineinteger-array: il tempo entro cui ogni attività deve essere completata, da 1 a n
profitinteger-array: quanto guadagna ciascun lavoro; profit[i] corrisponde a deadline[i]
Restituisceinteger: il profitto totale massimo dei lavori che possono essere completati tutti entro le rispettive scadenze

Vincoli

1 ≤ deadline.length == profit.length ≤ 5000
1 ≤ deadline[i] ≤ n, dove n è il numero di lavori
1 ≤ profit[i] ≤ 10⁵
Gli array non sono ordinati. Più lavori possono avere la stessa scadenza o lo stesso profitto.

Esempi

Input: deadline = [3, 1, 2, 3, 1]profit = [40, 35, 30, 25, 50]
Output: 120
Spiegazione: Solo uno dei due lavori con scadenza 1 può essere svolto, quindi esegui quello che vale 50. Il lavoro che vale 30 termina poi alla sua scadenza 2 e quello che vale 40 alla sua scadenza 3: 50 + 30 + 40 = 120.

Input: deadline = [1, 1, 1]profit = [5, 9, 7]
Output: 9
Spiegazione: Tutti e tre i lavori devono terminare entro il tempo 1, e prima di allora può essere completato un solo lavoro. Il migliore di questi vale 9.

Per approfondire

E se il lavoro i richiedesse duration[i] unità di tempo invece di una? Scegliere per primo il lavoro più redditizio dà ancora il miglior totale?

Soluzione

Scegli tu quali lavori tenere e quando eseguirli. Una regola greedy risolve entrambe le decisioni: prendi i lavori dal più redditizio al meno redditizio e colloca ciascuno nell’ultimo intervallo libero entro la sua scadenza, saltandolo se non ce n’è nessuno libero. Una struttura dati per insiemi disgiunti individua quell’intervallo senza passare oltre quelli già occupati.

Greedy in base al profitto, cercando uno slot libero

Intuizione

Suddividi il tempo in slot: lo slot t va da t-1 a t, un lavoro con scadenza d può usare gli slot da 1 a d e nessuna scadenza supera n. Scegliere per primo il lavoro più redditizio è sicuro: se tutti gli slot che potrebbe usare sono occupati, sostituirlo con il lavoro assegnato a uno di quegli slot rende almeno altrettanto. Assegnare lo slot più recente è sicuro perché solo gli slot iniziali sono utilizzabili dai lavori con scadenze ravvicinate.

Il costo è la scansione. Quando tutte le scadenze sono n, il k-esimo lavoro passa oltre k-1 slot occupati: circa n²/2, ovvero 12,5 milioni di passaggi con n = 5000.

Algoritmo

Ordina i lavori in base al profitto, dal più alto al più basso, mantenendo ogni scadenza insieme al relativo profitto.
Crea un array taken di n + 1 flag, tutti false.
Per ogni lavoro, procedi con t a ritroso dalla sua scadenza fino a 1 e fermati al primo slot che non è occupato.
Se ne hai trovato uno, contrassegnalo come occupato e aggiungi il profitto del lavoro a total.
Restituisci 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

Approccio greedy basato sul profitto con un insieme disgiunto di intervalli liberi

Intuizione

La scansione ripercorre continuamente gli stessi slot prenotati. Una struttura disjoint-set sugli slot da 0 a n li salta: parent[t] = t mentre lo slot t è libero, e prenotarlo imposta parent[t] = t-1, così seguendo i puntatori a partire da una scadenza si arriva all'ultimo slot libero. Raggiungere lo slot 0 significa che non ne rimane nessuno. La compressione a metà del percorso fa puntare ogni slot attraversato due passaggi più avanti, così i percorsi successivi sono più brevi.

Nel terzo esempio, i lavori del valore di 60 e 50 prenotano gli slot 2 e 1. Il lavoro del valore di 20, con scadenza 2, segue il percorso da 2 a 1 a 0 e viene saltato.

L'ordinamento costa O(n log n) e, con la compressione a metà del percorso, ogni ricerca costa O(log n) ammortizzato, quindi il totale rimane O(n log n).

Algoritmo

Ordina i lavori per profitto, dal più alto al più basso, mantenendo ogni scadenza associata al relativo profitto.
Imposta parent[t] = t per ogni slot t da 0 a n.
Per ogni lavoro, inizia da slot = deadline e segui parent finché parent[slot] == slot, dimezzando il percorso man mano.
Se slot > 0, aggiungi il profitto del lavoro e imposta parent[slot] = slot-1; altrimenti salta il lavoro.
Restituisci il totale.

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

Trappole e casi limite

Inserire un lavoro nel primo slot libero. Nel terzo esempio, il lavoro che vale 60 occuperebbe lo slot 1 e il lavoro che vale 50 andrebbe perso: 80 invece di 110.
Prendere i lavori in ordine di scadenza. Con scadenze [1, 1] e profitti [1, 100], il lavoro meno redditizio occupa l'unico slot e guadagni 1 invece di 100.
Dimensionare l'array degli slot con n invece di n + 1. Una scadenza pari a n farà quindi leggere oltre la fine dell'array.
Ordinare i profitti da soli. Ogni scadenza deve spostarsi insieme al proprio profitto.
Scrivere il passaggio di ricerca usando la ricorsione. Una catena che attraversa migliaia di slot occupati può causare un overflow dello stack; usa un ciclo.

Domande frequenti3

Qual è la complessità temporale del problema di sequenziamento dei lavori?

Con una struttura di insiemi disgiunti, il tempo è O(n log n), dominato dall’ordinamento, e lo spazio è O(n). Scorrere all’indietro a partire da ogni scadenza per trovare uno slot libero richiede O(n²) quando la maggior parte delle scadenze è lontana.

Perché l’approccio greedy funziona per la pianificazione dei lavori?

Alcuni calendari ottimali contengono il lavoro più redditizio. Se viene escluso e c'è uno slot libero prima della sua scadenza, aggiungerlo fa guadagnare di più; se tutti gli slot di questo tipo sono occupati, inserirlo al posto di un altro lavoro fa guadagnare almeno altrettanto. L'argomento si ripete per i lavori rimanenti.

È possibile risolvere il problema della pianificazione dei lavori usando invece un heap?

Sì. Ordina i lavori per scadenza e inserisci ogni profitto in un min-heap. Ogni volta che l’heap contiene più lavori di quanti ne consenta la scadenza corrente, rimuovi il profitto più basso. Alla fine, l’heap contiene il miglior insieme di lavori e la sua somma è la risposta, in O(n log n).

def jobSequencing(deadline, profit):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomenti

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

Output atteso