Task Scheduler

Q: Какова временная сложность Task Scheduler?

Подсчёт букв занимает O(m) для m задач, а затем формула считывает 26 счётчиков, поэтому решение работает за O(m) времени и использует O(1) дополнительной памяти. При симуляции с max-heap выполняется одно извлечение на каждую задачу — O(m log k) , где k ≤ 26 букв.

Q: Когда планировщику задач не требуется время простоя?

Когда m ≥ (top-1) × (n+1) + atTop , задачи занимают все свободные места и растягивают интервалы вместо того, чтобы оставлять пробелы, поэтому ответ — m . Пример 2, "ABCABD" при n = 1 — именно такой случай.

СреднеЖадные алгоритмы Куча Хеширование

+10

Дана строка tasks из заглавных букв, по одной букве на задачу, и целое число n. Процессор выполняет одну задачу за единицу времени в любом выбранном тобой порядке или простаивает в течение единицы времени.

Между двумя запусками задач с одной и той же буквой должно пройти не менее n единиц времени: букву, запущенную в момент t, можно запустить снова не раньше момента t+n+1. Верни минимальное количество единиц времени, необходимое для выполнения всех задач.

Функция

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

tasksstring: задания, по одной заглавной букве на каждое
ninteger: наименьшее количество единиц между двумя вхождениями одной и той же буквы
Возвращаетinteger: наименьшее количество единиц, включая бездействующие

Ограничения

1 ≤ tasks.length ≤ 10⁴
tasks содержит только заглавные буквы от A до Z.
0 ≤ n ≤ 100

Примеры

Ввод: tasks = "CACBAC"n = 2
Вывод: 7
Пояснение: C выполняется три раза с двумя единицами между запусками, поэтому только его запуски занимают 7 единиц. Порядок C A B C A, простой, C заполняет промежутки с помощью A и B и требует одну единицу простоя: 7.

Ввод: tasks = "ABCABD"n = 1
Вывод: 6
Пояснение: A и B выполняются по два раза, с одной единицей между запусками. Порядок A B C A B D разделяет их без какого-либо простоя на единицу, поэтому ответ — количество задач: 6.

Ввод: tasks = "ZZZ"n = 3
Вывод: 9
Пояснение: Выполняться может только Z, поэтому каждый промежуток — это простой: Z, три единицы простоя, Z, три единицы простоя, Z. Это 9 единиц.

Дополнительный вопрос

Можешь также вернуть одно расписание минимальной длины в виде строки, где для каждой единицы простоя используется .?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Порядок выбираешь ты, поэтому вопрос в том, сколько минимум единиц простоя тебе потребуется. Всё решает самая часто встречающаяся буква: её серии должны располагаться на расстоянии n+1 единиц друг от друга, а остальные задачи заполняют промежутки между ними. Сначала выполняй задачи с самыми часто встречающимися буквами, используя max-heap, или напрямую подсчитай промежутки по одной формуле.

Моделируйте раунды с помощью max-heap

Идея

Разбей время на раунды по n+1 единиц. В каждом раунде буква может выполняться не более одного раза, а буква на некотором месте в одном раунде может выполняться снова на том же месте в следующем — ровно через n+1 единиц времени. В каждом раунде выполняй буквы, у которых осталось больше всего копий. Интервалы между их оставшимися выполнениями должны составлять n+1, поэтому именно они могут вынудить простаивать в конце; если выполнять их первыми, количество оставшихся копий будет выравниваться.

Раунд, после которого остаются задачи, длится n+1 единиц времени: пустые места в нём — простой; последний раунд длится только столько, сколько занимают выполненные в нём задачи. В примере 1 в раундах выполняются C A B, затем C A и одна единица простоя, затем последняя C: 3 + 3 + 1 = 7. Каждое извлечение выполняет одну задачу, поэтому при m задачах и k ≤ 26 буквах сложность составляет O(m log k).

Алгоритм

Посчитай количество каждой буквы и помести значения больше нуля в max-кучу.
Пока куча не пуста, выполняй раунд: извлеки до n+1 значений и оставь каждое значение минус один, если оно всё ещё больше нуля.
Верни оставленные значения в кучу.
Добавь n+1 ко времени, если куча не пуста; иначе добавь количество задач, выполненных за раунд.
Верни время.

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

Посчитайте количество кадров для самой часто встречающейся буквы

Идея

Пусть top — наибольшее количество, которое встречается у буквы X. Расположи X так, чтобы после каждого блока, кроме последнего, оставалось n свободных мест: top-1 блоков по n+1 единиц, затем последний блок X. Буква, у которой меньше top копий, помещается в свободные места — по одной копии на блок, — поэтому между её копиями остаётся не менее n+1 единиц. Каждая другая буква с top копиями добавляет одну единицу в конце. Если букв с наибольшим количеством копий atTop, получится (top-1) × (n+1) + atTop единиц.

Расписание не может быть короче: раздели первые (top-1) × (n+1) единиц на top-1 окон по n+1. Каждая буква с максимальным количеством копий встречается не более одного раза в каждом окне, поэтому после окон у всех этих atTop букв останется ещё по одному блоку. Если задач больше, чем свободных мест, увеличь некоторые блоки до размера больше n+1. Более длинный блок только увеличивает промежутки, поэтому простоя не будет, а ответом будет m. Ответ — большее из двух значений.

Алгоритм

Посчитай каждую из 26 букв.
Найди top — наибольшее количество, и atTop — сколько букв имеют такое количество.
Вычисли frames = (top-1) × (n+1) + atTop.
Верни большее из значений frames и количества задач.

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

Ловушки и крайние случаи

Забывая учитывать буквы, разделившие первое место. В "MMNNPP" при n = 5 у всех трёх букв количество равно 2, поэтому ответ — (2-1) × 6 + 3 = 9, а не 7.
Забывая выбрать большее из значений. В примере 2 интервалы дают (2-1) × 2 + 2 = 4, но для шести задач нужно шесть единиц.
Отводя последнему раунду целые n+1 единиц. После последней задачи ничего не ожидает: в примере 3 получилось бы 12 вместо 9.
Возвращая количество обратно внутрь раунда. Тогда ту же букву можно снова извлечь в этом раунде и выполнить дважды с слишком коротким интервалом.

Частые вопросы3

Какова временная сложность Task Scheduler?

Подсчёт букв занимает O(m) для m задач, а затем формула считывает 26 счётчиков, поэтому решение работает за O(m) времени и использует O(1) дополнительной памяти. При симуляции с max-heap выполняется одно извлечение на каждую задачу — O(m log k), где k ≤ 26 букв.

Когда планировщику задач не требуется время простоя?

Когда m ≥ (top-1) × (n+1) + atTop, задачи занимают все свободные места и растягивают интервалы вместо того, чтобы оставлять пробелы, поэтому ответ — m. Пример 2, "ABCABD" при n = 1 — именно такой случай.

Имеет ли значение порядок символов во входной строке?

Нет. Вы выбираете порядок, в котором процессор выполняет задачи, поэтому важно только, сколько раз встречается каждая буква. "CACBAC" и "CCCAAB" при n = 2 требуют по 7 единиц.

def leastInterval(tasks, n):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргументы

tasks = "CACBAC"
n = 2

Ожидаемый вывод