Job Sequencing Problem

Q: Qual é a complexidade de tempo do problema de sequenciamento de tarefas?

Com um conjunto disjunto, o tempo é O(n log n) , dominado pela ordenação, e o espaço é O(n) . Percorrer de trás para frente a partir de cada prazo para encontrar um horário livre custa O(n²) quando a maioria dos prazos é grande.

MédioGuloso Ordenação

+10

Você recebe n trabalhos como dois arrays: o trabalho i rende profit[i] se for concluído até o prazo deadline[i]. Cada trabalho leva uma unidade de tempo, você executa um trabalho por vez começando no tempo 0 e pode pular qualquer trabalho. Um trabalho com prazo 2 pode ser executado de 0 a 1 ou de 1 a 2.

Retorne o maior lucro total que você pode obter.

Função

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

deadlineinteger-array: o prazo até o qual cada tarefa deve ser concluída, de 1 a n
profitinteger-array: quanto cada trabalho rende; profit[i] pertence a deadline[i]
Retornainteger: o maior lucro total de trabalhos que podem ser concluídos até seus prazos

Restrições

1 ≤ deadline.length == profit.length ≤ 5000
1 ≤ deadline[i] ≤ n, em que n é o número de tarefas
1 ≤ profit[i] ≤ 10⁵
Os arrays não estão ordenados. Vários trabalhos podem ter o mesmo prazo ou lucro.

Exemplos

Entrada: deadline = [3, 1, 2, 3, 1]profit = [40, 35, 30, 25, 50]
Saída: 120
Explicação: Apenas um dos dois trabalhos com prazo 1 cabe, então execute o que vale 50. O trabalho que vale 30 termina então no prazo 2, e o trabalho que vale 40, no prazo 3: 50 + 30 + 40 = 120.

Entrada: deadline = [1, 1, 1]profit = [5, 9, 7]
Saída: 9
Explicação: Os três trabalhos precisam terminar até o instante 1, e apenas um deles cabe antes disso. O melhor deles rende 9.

Para ir além

E se o trabalho i levar duration[i] unidades de tempo em vez de uma? Escolher primeiro o trabalho mais lucrativo ainda resulta no melhor total?

Solução

Você escolhe quais trabalhos manter e quando executá-los. Uma regra gulosa resolve ambos: pegue os trabalhos começando pelos mais lucrativos e coloque cada um no horário livre mais tardio até seu prazo, ignorando-o quando não houver nenhum horário livre. Uma estrutura de conjuntos disjuntos encontra esse horário sem percorrer os já ocupados.

Ganancioso por lucro, procurando um horário livre

Intuição

Divida o tempo em intervalos: o intervalo t vai de t-1 a t, um trabalho com prazo d pode usar os intervalos de 1 a d, e nenhum prazo excede n. Escolher primeiro o trabalho mais lucrativo é seguro: se todos os intervalos que ele poderia usar estiverem ocupados, trocá-lo pelo trabalho em um deles rende pelo menos o mesmo. Reservar o intervalo mais tardio é seguro porque os intervalos iniciais são os únicos que trabalhos com prazos curtos podem usar.

O custo está na busca. Quando todos os prazos são n, o k-ésimo trabalho passa por k-1 intervalos ocupados: cerca de n²/2, ou 12,5 milhões de etapas quando n = 5000.

Algoritmo

Ordene os trabalhos pelo lucro, do maior para o menor, mantendo cada prazo junto com seu lucro.
Crie um array taken de n + 1 sinalizadores, todos false.
Para cada trabalho, percorra t em ordem decrescente, do prazo até 1, e pare no primeiro intervalo que não estiver ocupado.
Se encontrar um, marque-o como ocupado e adicione o lucro do trabalho a total.
Retorne 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

Algoritmo guloso pelo lucro com uma estrutura de conjuntos disjuntos de horários livres

Intuição

A varredura percorre repetidamente os mesmos horários reservados. Uma estrutura de conjuntos disjuntos sobre os horários de 0 a n os ignora: parent[t] = t enquanto o horário t estiver livre, e reservá-lo define parent[t] = t-1, de modo que seguir os ponteiros a partir de um prazo leva ao horário livre mais recente. Chegar ao horário 0 significa que não há mais nenhum disponível. A compressão de caminho pela metade aponta cada horário percorrido dois passos adiante, tornando as caminhadas posteriores mais curtas.

No terceiro exemplo, os trabalhos que valem 60 e 50 reservam os horários 2 e 1. O trabalho que vale 20, com prazo 2, segue de 2 para 1 e depois para 0, sendo ignorado.

A ordenação custa O(n log n) e, com a compressão de caminho pela metade, cada consulta custa O(log n) amortizado, então o custo total permanece O(n log n).

Algoritmo

Ordene os trabalhos pelo lucro, do maior para o menor, mantendo cada prazo junto do seu lucro.
Defina parent[t] = t para cada intervalo t de 0 a n.
Para cada trabalho, comece em slot = deadline e siga parent até que parent[slot] == slot, reduzindo o caminho pela metade à medida que avança.
Se slot > 0, some o lucro do trabalho e defina parent[slot] = slot-1; caso contrário, ignore o trabalho.
Retorne o 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

Armadilhas e casos extremos

Colocar um trabalho no primeiro espaço livre. No terceiro exemplo, o trabalho que vale 60 ocuparia o espaço 1, e o trabalho que vale 50 seria perdido: 80 em vez de 110.
Selecionar os trabalhos na ordem dos prazos. Com os prazos [1, 1] e os lucros [1, 100], o trabalho de baixo valor ocupa o único espaço, e você ganha 1 em vez de 100.
Dimensionar o array de espaços como n em vez de n + 1. Um prazo igual a n então tenta ler além do fim.
Ordenar os lucros separadamente. Cada prazo precisa se mover junto com seu lucro.
Escrever a etapa de busca com recursão. Uma cadeia que percorre milhares de espaços ocupados pode estourar a pilha; use um loop.

Perguntas frequentes3

Qual é a complexidade de tempo do problema de sequenciamento de tarefas?

Com um conjunto disjunto, o tempo é O(n log n), dominado pela ordenação, e o espaço é O(n). Percorrer de trás para frente a partir de cada prazo para encontrar um horário livre custa O(n²) quando a maioria dos prazos é grande.

Por que a abordagem gulosa funciona para o sequenciamento de tarefas?

Alguma programação ótima contém o trabalho mais lucrativo. Se ele ficar de fora e houver um horário livre antes do prazo, adicioná-lo rende mais; se todos esses horários estiverem ocupados, substituí-lo rende pelo menos o mesmo. O argumento se repete para os trabalhos restantes.

É possível resolver o sequenciamento de tarefas usando um heap?

Sim. Ordene os trabalhos por prazo e insira cada lucro em um min-heap. Sempre que o heap contiver mais trabalhos do que o prazo atual permite, remova o menor lucro. No final, o heap contém o melhor conjunto de trabalhos, e a soma deles é a resposta, em O(n log n).

def jobSequencing(deadline, profit):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumentos

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

Saída Esperada