7. Task Scheduler

«Искусство планирования состоит в том, чтобы заставить неизбежные паузы работать на общую цель».
— Эдсгер Дейкстра

Жадное планирование: CPU и минимизация простоев

Кучи лежат в основе любого промышленного планировщика задач (OS CPU Scheduler, Go Runtime Scheduler, Kubernetes kube-scheduler).
Задача Task Scheduler (LeetCode №621) моделирует процесс распределения задач на процессоре с учетом фиксированного периода охлаждения (cooldown).

Условие: Задан массив символов tasks, представляющий однотипные задачи (например, 'A', 'B'), и неотрицательное число $n$ (период кулдауна).
Между двумя одинаковыми задачами должно пройти не менее $n$ интервалов времени. В эти интервалы процессор может либо выполнять другую доступную задачу, либо простаивать (idle).
Требуется определить минимальное суммарное время, необходимое для выполнения всех задач.

Стратегия: Жадный выбор наиболее частой задачи

Интуиция оптимального планирования: паузы (idle) возникают исключительно из-за кулдауна наиболее часто встречающихся задач. Следовательно, в каждый момент времени процессор обязан выбирать задачу с максимальным оставшимся числом повторений. Это оставляет наибольшее разнообразие для заполнения будущих пауз.

Для динамического извлечения наиболее частой задачи используется Max-Heap, а для отслеживания задач на кулдауне — очередь FIFO.

flowchart LR
    classDef process fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef success fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
    classDef warning fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc

    Heap["Max-Heap:<br>Задачи, готовые к исполнению"]:::success -->|"Извлечение максимума"| CPU["CPU:<br>Выполнение 1 такта"]:::process
    CPU -->|"Кулдаун n тактов"| Cooldown["Очередь ожидания:<br>(остаток, время разморозки)"]:::warning
    Cooldown -->|"Время вышло"| Heap
  

Реализация 1: Симуляция через Max-Heap и Очередь

package main

import "container/heap"

type MaxHeap []int

func (h MaxHeap) Len() int           { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i] > h[j] } // Max-Heap
func (h MaxHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x any)        { *h = append(*h, x.(int)) }
func (h *MaxHeap) Pop() any {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

type CooldownTask struct {
    count     int
    readyTime int
}

// leastInterval симулирует планировщик через Max-Heap и очередь кулдауна.
func leastInterval(tasks []byte, n int) int {
    if n == 0 {
        return len(tasks)
    }

    freq := make(map[byte]int)
    for _, t := range tasks {
        freq[t]++
    }

    h := &MaxHeap{}
    for _, count := range freq {
        heap.Push(h, count)
    }

    time := 0
    queue := make([]CooldownTask, 0, n+1)

    for h.Len() > 0 || len(queue) > 0 {
        time++

        if h.Len() > 0 {
            count := heap.Pop(h).(int) - 1
            if count > 0 {
                queue = append(queue, CooldownTask{count: count, readyTime: time + n})
            }
        }

        if len(queue) > 0 && queue[0].readyTime == time {
            heap.Push(h, queue[0].count)
            queue = queue[1:]
        }
    }

    return time
}

Реализация 2: Математическая формула за O(N) времени и O(1) памяти

На Senior-интервью часто ожидают вывод аналитической формулы расчета времени без пошаговой симуляции:

1. Находим максимальную частоту задачи $f_{\max}$ (например, задача 'A' встречается $3$ раза).
2. Находим количество задач с этой максимальной частотой $k_{\max}$.
3. Минимальное время определяется каркасом из $f_{\max} - 1$ блоков длины $n + 1$ плюс финальный неполный блок:
   $$\text{time} = (f_{\max} - 1) \times (n + 1) + k_{\max}$$
4. Если свободных задач достаточно, чтобы полностью заполнить все паузы без простоев, ответ равен общей длине len(tasks).

package main

func leastIntervalMath(tasks []byte, n int) int {
    counts := [26]int{}
    maxFreq := 0
    for _, t := range tasks {
        counts[t-'A']++
        if counts[t-'A'] > maxFreq {
            maxFreq = counts[t-'A']
        }
    }

    maxCount := 0
    for _, count := range counts {
        if count == maxFreq {
            maxCount++
        }
    }

    totalSlots := (maxFreq-1)*(n+1) + maxCount
    if totalSlots < len(tasks) {
        return len(tasks)
    }
    return totalSlots
}

Резюме раздела «Кучи и Top K»

1. Бинарная куча в плоском срезе: $O(1)$ для чтения экстремума, $O(\log N)$ для вставки/извлечения, $O(N)$ для построения через heap.Init.
2. Top K инвариант: Для поиска максимумов используется Min-Heap; для поиска минимумов — Max-Heap.
3. Две кучи: Паттерн разделения потока на две половины обеспечивает динамический поиск медианы за $O(1)$.

Далее мы переходим к классу алгоритмов, принимающих локально оптимальные решения на каждом шаге: 1. Теория. Жадные алгоритмы.