​​Ускоряем O(N + T), не меняя Big O. Часть 1. Разностный массив — это только начало

На прошлой неделе просочился черновик, самые внимательные успели увидеть «исходники» не в 8-битном формате. Теперь же пора восстановиться по-настоящему.

Сегодня тема особенно интересная. Многие видели, слышали, а может, и участвовали в CodeRun Summer от нашей любимой алгоритмической компании. Но в этот раз цель не просто решить задачу, а сделать это максимально эффективно.

И что может быть эффективнее, чем JavaScript?

Начнем нашу историю с первой задачи (спойлер: решений не будет, пока идет соревнование). Итак, прокат велосипедов. Классическая задача на планирование ресурсов или же интервальная задача.

Краткое условие: есть временная шкала и заявки с моментом начала, окончания и количеством велосипедов. Требуется найти максимальное количество велосипедов, которые одновременно понадобятся. И при этом интервал полуоткрытый, т.е. в момент завершения велосипеды уже свободны.

Решение в лоб

Можно для каждой заявки пройти по всему интервалу и прибавить s:

for (const [a, f, s] of rentals) {
  for (let time = a; time < f; time++) {
    bikes[time] += s;
  }
}

В худшем случае почти каждая заявка занимает всю временную шкалу.

Ограничения ясно показывают, почему решение в лоб не подойдет: N и T могут достигать 10 миллионов.

Получаем сложность O(N × T) и надежный способ познакомиться с Time Limit.

Вспоминаем разностный массив

Вместо изменения каждой точки сохраним только два события:

diff[a] += s;
diff[f] -= s;

После обработки всех заявок один раз пройдем по массиву и восстановим значения префиксной суммой:

let current = 0;
let answer = 0;

for (let time = 0; time < T; time++) {
  current += diff[time];

  if (current > answer) {
    answer = current;
  }
}

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

Этот паттерн я уже подробнее разбирал в статье Разностные массивы. Там же есть визуальный пример такой отложенной симуляции.

Сложность нового решения складывается из обработки N заявок — O(N) и восстановления временной шкалы — O(T).

Итого — O(N + T).

Теперь же нажимает Submit и идет пить кофе, получаем базовое решение 1.589 секунды.

В следующей части начнем с простого вопроса: зачем хранить числа в восьми байтах, если почти все они помещаются в четыре?

И почему попытка сэкономить память внезапно превращает положительные числа в отрицательные.

#JavaScript #NodeJS #Algorithms #DifferenceArray #Performance #CodeRun #8BitJS