Task Scheduler

Q: ¿Cuál es la complejidad temporal de Task Scheduler?

Contar las letras requiere O(m) para m tareas, y después la fórmula lee 26 recuentos, así que la solución tiene un tiempo de O(m) y usa O(1) de memoria adicional. La simulación del montículo máximo extrae un elemento por tarea, O(m log k) con k ≤ 26 letras.

Q: ¿Cuándo no necesita tiempo de inactividad el Programador de tareas?

Cuando m ≥ (top-1) × (n+1) + atTop , las tareas llenan todos los espacios abiertos y alargan los marcos en lugar de dejar huecos, así que la respuesta es m . El ejemplo 2, "ABCABD" con n = 1 , es un caso así.

MedioVoraz Montículo Hashing

+10

Recibes una cadena tasks de letras mayúsculas, una letra por tarea, y un entero n. Un procesador ejecuta una tarea por unidad de tiempo, en el orden que elijas, o permanece inactivo durante una unidad.

Entre dos ejecuciones de la misma letra debe haber al menos n unidades: una letra que se ejecuta en la unidad t puede volver a ejecutarse como pronto en la unidad t+n+1. Devuelve el menor número de unidades que permite ejecutar todas las tareas.

Función

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

tasksstring: las tareas, una letra mayúscula cada una
ninteger: el menor número de unidades entre dos apariciones de la misma letra
Devuelveinteger: el menor número de unidades, incluidas las inactivas

Restricciones

1 ≤ tasks.length ≤ 10⁴
tasks contiene solo las letras mayúsculas de la A a la Z.
0 ≤ n ≤ 100

Ejemplos

Entrada: tasks = "CACBAC"n = 2
Salida: 7
Explicación: C se ejecuta tres veces con dos unidades entre ejecuciones, así que sus ejecuciones abarcan 7 unidades. El orden C A B C A, con un tiempo inactivo, llena los huecos con A y B y necesita una unidad de tiempo inactivo: 7.

Entrada: tasks = "ABCABD"n = 1
Salida: 6
Explicación: A y B se ejecutan dos veces cada uno, con una unidad entre ejecuciones. El orden A B C A B D los mantiene separados sin ninguna unidad inactiva, así que la respuesta es el número de tareas, 6.

Entrada: tasks = "ZZZ"n = 3
Salida: 9
Explicación: Solo hay Z para ejecutar, así que cada intervalo está inactivo: Z, tres unidades inactivas, Z, tres unidades inactivas, Z. Eso son 9 unidades.

Para ir más allá

¿También puedes devolver un cronograma de la menor duración, como una cadena con un . por cada unidad inactiva?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Tú eliges el orden, así que la pregunta es cuántas unidades inactivas necesitas como mínimo. La letra más frecuente lo determina: sus ejecuciones deben quedar separadas por n+1 unidades, y las demás tareas llenan los espacios entre ellas. Ejecuta primero las letras más frecuentes con un montículo máximo, o cuenta directamente los espacios con una fórmula.

Simula rondas con un montículo máximo

Intuición

Divide el tiempo en rondas de n+1 unidades. Ninguna letra puede ejecutarse dos veces en una ronda, y una letra en una posición de una ronda puede volver a ejecutarse en la misma posición de la siguiente, exactamente n+1 unidades después. En cada ronda, ejecuta las letras de las que queden más copias. Sus ejecuciones restantes deben mantenerse separadas por n+1, así que son las que pueden obligar a dejar tiempo inactivo al final; ejecutarlas primero mantiene equilibrados los recuentos.

Una ronda que deja tareas pendientes cuesta n+1 unidades, y sus espacios vacíos quedan inactivos; la última ronda cuesta solo las tareas que ejecutó. En el ejemplo 1, las rondas ejecutan C A B, luego C A y una unidad inactiva, y luego la última C: 3 + 3 + 1 = 7. Cada extracción ejecuta una tarea, así que con m tareas y k ≤ 26 letras, esto es O(m log k).

Algoritmo

Cuenta cada letra y coloca los conteos mayores que cero en un montículo máximo.
Mientras el montículo no esté vacío, ejecuta una ronda: extrae hasta n+1 conteos y conserva cada conteo menos uno que siga siendo mayor que cero.
Vuelve a insertar los conteos conservados.
Suma n+1 al tiempo si el montículo no está vacío; de lo contrario, suma la cantidad de tareas que ejecutó la ronda.
Devuelve el tiempo.

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

Cuenta las apariciones de la letra más frecuente

Intuición

Sea top el recuento más alto, alcanzado por la letra X. Dispón las X dejando n espacios abiertos después de cada secuencia, excepto la última: top-1 bloques de n+1 unidades, seguidos de la última secuencia de X. Una letra con menos de top copias cabe en los espacios abiertos, una copia por bloque, de modo que sus copias quedan separadas por al menos n+1. Cada una de las demás letras con top copias añade una unidad al final. Con atTop letras con el recuento más alto, eso equivale a (top-1) × (n+1) + atTop unidades.

Ninguna planificación es más corta: divide las primeras (top-1) × (n+1) unidades en top-1 ventanas de n+1. Cada letra con el recuento más alto aparece como máximo una vez por ventana, así que a las atTop todavía les queda una aparición después de las ventanas. Si hay más tareas que espacios abiertos, deja que algunos bloques se alarguen más de n+1. Un bloque más largo solo amplía los intervalos, así que no hay inactividad y la respuesta es m. La respuesta es la mayor de las dos.

Algoritmo

Cuenta cada una de las 26 letras.
Encuentra top, el recuento más alto, y atTop, cuántas letras lo tienen.
Calcula frames = (top-1) × (n+1) + atTop.
Devuelve el mayor entre frames y el número de tareas.

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))

Errores comunes y casos límite

Olvidar las letras empatadas en el primer puesto. En "MMNNPP" con n = 5, las tres letras tienen un conteo de 2, así que la respuesta es (2-1) × 6 + 3 = 9, no 7.
Olvidar el paso de tomar el mayor valor. En el ejemplo 2, los intervalos dan (2-1) × 2 + 2 = 4, pero seis tareas necesitan seis unidades.
Asignar a la última ronda n+1 unidades completas. No hay que esperar después de la última tarea: el ejemplo 3 daría 12 en lugar de 9.
Volver a introducir un conteo en la ronda. Entonces se puede extraer la misma letra otra vez en esa ronda y ejecutarla dos veces demasiado seguidas.

Preguntas frecuentes3

¿Cuál es la complejidad temporal de Task Scheduler?

Contar las letras requiere O(m) para m tareas, y después la fórmula lee 26 recuentos, así que la solución tiene un tiempo de O(m) y usa O(1) de memoria adicional. La simulación del montículo máximo extrae un elemento por tarea, O(m log k) con k ≤ 26 letras.

¿Cuándo no necesita tiempo de inactividad el Programador de tareas?

Cuando m ≥ (top-1) × (n+1) + atTop, las tareas llenan todos los espacios abiertos y alargan los marcos en lugar de dejar huecos, así que la respuesta es m. El ejemplo 2, "ABCABD" con n = 1, es un caso así.

¿Importa el orden de la cadena de entrada?

No. Tú eliges el orden en que el procesador ejecuta las tareas, así que solo importa cuántas veces aparece cada letra. "CACBAC" y "CCCAAB" con n = 2 necesitan ambos 7 unidades.

def leastInterval(tasks, n):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumentos

tasks = "CACBAC"
n = 2

Salida Esperada