Task Scheduler

Q: Qual é a complexidade de tempo do Task Scheduler?

Contar as letras leva O(m) para m tarefas, e a fórmula então lê 26 contagens, portanto a solução tem complexidade de tempo O(m) e usa O(1) de memória extra. A simulação com max-heap remove um elemento por tarefa, O(m log k) com k ≤ 26 letras.

Q: Quando o Agendador de Tarefas não precisa de tempo ocioso?

Quando m ≥ (top-1) × (n+1) + atTop , as tarefas preenchem todos os espaços disponíveis e esticam os quadros em vez de deixar lacunas, então a resposta é m . O Exemplo 2, "ABCABD" com n = 1 , é um caso desse tipo.

MédioGuloso Heap Hashing

+10

Você recebe uma string tasks de letras maiúsculas, uma letra por tarefa, e um número inteiro n. Um processador executa uma tarefa por unidade de tempo, em qualquer ordem que você escolher, ou fica ocioso durante uma unidade.

Entre duas execuções da mesma letra, são necessárias pelo menos n unidades: uma letra executada na unidade t pode ser executada novamente, no mínimo, na unidade t+n+1. Retorne o menor número de unidades necessário para executar todas as tarefas.

Função

leastInterval(tasks: string, n: integer) → integer

tasksstring: as tarefas, uma letra maiúscula cada
ninteger: o menor número de unidades entre duas sequências da mesma letra
Retornainteger: o menor número de unidades, incluindo as ociosas

Restrições

1 ≤ tasks.length ≤ 10⁴
tasks contém apenas letras maiúsculas de A a Z.
0 ≤ n ≤ 100

Exemplos

Entrada: tasks = "CACBAC"n = 2
Saída: 7
Explicação: C é executado três vezes com duas unidades entre as execuções, então apenas suas execuções ocupam 7 unidades. A ordem C A B C A, ocioso, C preenche os intervalos com A e B e precisa de uma unidade ociosa: 7.

Entrada: tasks = "ABCABD"n = 1
Saída: 6
Explicação: A e B são executadas duas vezes cada, com uma unidade entre as execuções. A ordem A B C A B D mantém A e B separadas sem nenhuma unidade ociosa, então a resposta é o número de tarefas, 6.

Entrada: tasks = "ZZZ"n = 3
Saída: 9
Explicação: Só há Z para executar, então cada intervalo fica ocioso: Z, três unidades ociosas, Z, três unidades ociosas, Z. Isso dá 9 unidades.

Para ir além

Você também pode retornar um cronograma de menor duração, como uma string com um . para cada unidade ociosa?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Você escolhe a ordem, então a questão é quantas unidades ociosas são necessárias, no mínimo. A letra mais frequente determina isso: suas ocorrências devem ficar a n+1 unidades de distância, e as outras tarefas preenchem os intervalos entre elas. Execute primeiro as letras mais frequentes usando um max-heap ou conte os intervalos diretamente em uma única fórmula.

Simule rodadas com um heap máximo

Intuição

Divida o tempo em rodadas de n+1 unidades. Nenhuma letra pode ser executada duas vezes em uma rodada, e uma letra em determinada posição de uma rodada pode ser executada novamente na mesma posição da rodada seguinte, exatamente n+1 unidades depois. Em cada rodada, execute as letras que ainda têm mais ocorrências. As execuções restantes delas devem ficar separadas por n+1, então são elas que podem forçar tempo ocioso no final; executá-las primeiro mantém as contagens equilibradas.

Uma rodada que deixa tarefas pendentes custa n+1 unidades, com seus espaços vazios ociosos; a última rodada custa apenas as tarefas que executou. No exemplo 1, as rodadas executam C A B, depois C A e uma unidade ociosa, e então o último C: 3 + 3 + 1 = 7. Cada remoção executa uma tarefa, então, com m tarefas e k ≤ 26 letras, isso é O(m log k).

Algoritmo

Conte cada letra e coloque as contagens maiores que zero em um heap máximo.
Enquanto o heap não estiver vazio, execute uma rodada: remova até n+1 contagens e mantenha cada contagem menos um que ainda seja maior que zero.
Insira novamente as contagens mantidas.
Adicione n+1 ao tempo se o heap não estiver vazio; caso contrário, adicione a quantidade de tarefas executadas na rodada.
Retorne o tempo.

import heapq
from collections import Counter


def leastInterval(tasks, n):
    # heapq is a min-heap, so store negated counts to pop the largest first.
    heap = [-c for c in Counter(tasks).values()]
    heapq.heapify(heap)
    time = 0
    while heap:
        # One round of n+1 slots: run the most frequent tasks left, each at most once.
        left = []
        ran = 0
        while ran < n + 1 and heap:
            c = -heapq.heappop(heap)
            ran += 1
            if c > 1:
                left.append(c - 1)
        for c in left:
            heapq.heappush(heap, -c)
        # A round lasts n+1 units, idle included; the last one ends with its last task.
        time += n + 1 if heap else ran
    return time

Conte os quadros da letra mais frequente

Intuição

Seja top a maior contagem, alcançada pela letra X. Organize X com n posições livres após cada sequência, exceto a última: top-1 quadros de n+1 unidades, seguidos pela última sequência de X. Uma letra com menos de top cópias cabe nas posições livres, uma cópia por quadro, então suas cópias ficam separadas por pelo menos n+1. Cada outra letra com top cópias acrescenta uma unidade ao final. Com atTop letras na contagem mais alta, isso corresponde a (top-1) × (n+1) + atTop unidades.

Nenhum escalonamento é mais curto: divida as primeiras (top-1) × (n+1) unidades em top-1 janelas de n+1. Cada letra com a contagem mais alta aparece no máximo uma vez por janela, então todas as atTop ainda terão uma sequência restante após as janelas. Se houver mais tarefas do que posições livres, deixe alguns quadros ultrapassarem n+1. Um quadro mais longo apenas aumenta os intervalos, então nada fica ocioso e a resposta é m. A resposta é o maior dos dois valores.

Algoritmo

Conte cada uma das 26 letras.
Encontre top, a contagem mais alta, e atTop, quantas letras têm essa contagem.
Calcule frames = (top-1) × (n+1) + atTop.
Retorne o maior valor entre frames e o número de tarefas.

def leastInterval(tasks, n):
    counts = [0] * 26
    for ch in tasks:
        counts[ord(ch) - ord("A")] += 1
    top = max(counts)
    at_top = counts.count(top)  # tasks that share the highest count
    # top-1 full frames of n+1 units, then one last slot per task at the top count.
    frames = (top - 1) * (n + 1) + at_top
    # With more tasks than frame slots, no idle unit is needed at all.
    return max(frames, len(tasks))

Armadilhas e casos extremos

Esquecer as letras empatadas no topo. Em "MMNNPP" com n = 5, as três letras têm contagem 2, então a resposta é (2-1) × 6 + 3 = 9, não 7.
Esquecer a etapa de escolher o maior valor. No exemplo 2, os quadros resultam em (2-1) × 2 + 2 = 4, mas seis tarefas precisam de seis unidades.
Cobrar n+1 unidades completas na última rodada. Nada espera após a última tarefa: o exemplo 3 resultaria em 12 em vez de 9.
Colocar uma contagem de volta dentro da rodada. Assim, a mesma letra pode ser retirada novamente nessa rodada e executada duas vezes com um intervalo muito curto.

Perguntas frequentes3

Qual é a complexidade de tempo do Task Scheduler?

Contar as letras leva O(m) para m tarefas, e a fórmula então lê 26 contagens, portanto a solução tem complexidade de tempo O(m) e usa O(1) de memória extra. A simulação com max-heap remove um elemento por tarefa, O(m log k) com k ≤ 26 letras.

Quando o Agendador de Tarefas não precisa de tempo ocioso?

Quando m ≥ (top-1) × (n+1) + atTop, as tarefas preenchem todos os espaços disponíveis e esticam os quadros em vez de deixar lacunas, então a resposta é m. O Exemplo 2, "ABCABD" com n = 1, é um caso desse tipo.

A ordem da string de entrada importa?

Não. Você escolhe a ordem em que o processador executa as tarefas, então só importa quantas vezes cada letra aparece. "CACBAC" e "CCCAAB" com n = 2 precisam de 7 unidades.

def leastInterval(tasks, n):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumentos

tasks = "CACBAC"
n = 2

Saída Esperada