Паттерн: Жадность

Признак в условии

• «максимум / минимум», и локально лучший выбор не мешает будущему
• задачи про прыжки, покрытие, расписание, размен при «правильных» номиналах
• часто после сортировки становится очевидно

Идея

На каждом шаге берём лучшее прямо сейчас и не пересматриваем. Работает, только если у задачи есть свойство жадного выбора. Проверяй контрпримером: для размена монетами [1, 3, 4] и суммы 6 жадность даст 3 монеты вместо 2 - здесь нужна динамика.

Шаблон

let reach = 0;
for (let i = 0; i < nums.length; i++) {
  if (i > reach) return false;        // проверка ДО обновления
  reach = Math.max(reach, i + nums[i]);
}
return true;

Сложность

Обычно O(n) или O(n log n) с сортировкой, память O(1).

Частые ошибки

• жадность применяется там, где нужна динамика - всегда ищи контрпример
• проверка выполняется после обновления состояния
• забыта сортировка, без которой жадный выбор неверен

Мнемоника

«Лучшее сейчас - и не оглядываться»

Не путать с

• Динамическое программирование - прежде чем брать жадность, попробуй найти контрпример вслух. Не нашёл - говори «жадно, потому что…»; нашёл - динамика
• Интервалы - классическая жадность на отрезках: сортируем по концу и берём первый подходящий

Задачи на этот паттерн

• можно ли дойти до конца
• лучшая сделка
• круговой маршрут
• разбиение строки на части

Суть

Жадный алгоритм на каждом шаге берёт лучшее «прямо сейчас» и не пересматривает решение. Он быстрый и короткий, но верен не всегда. Главная часть ответа на собесе: объяснить, почему жадность тут работает.

Как распознать по условию

• «максимум / минимум чего-то» и после сортировки выбор очевиден;
• интервалы: «максимум непересекающихся», «минимум стрел»;
• «можно ли дойти», «минимум прыжков»;
• распределение ресурса: печенья детям, лодки для людей;
• прибыль с акциями при неограниченных сделках.

Шаблон: сортировка + проход

function maxNonOverlapping(intervals) {
  intervals.sort((a, b) => a[1] - b[1]);   // по концу
  let count = 0, end = -Infinity;
  for (const [s, e] of intervals) {
    if (s >= end) { count++; end = e; }
  }
  return count;
}

Шаблон: поддержка «самого дальнего»

function canJump(nums) {
  let far = 0;
  for (let i = 0; i < nums.length; i++) {
    if (i > far) return false;
    far = Math.max(far, i + nums[i]);
  }
  return true;
}

Как обосновать

1. Обменный аргумент: возьми любое оптимальное решение; замени его первый шаг жадным; покажи, что хуже не стало.
2. Жадный не отстаёт: после каждого шага жадное решение не хуже любого другого по выбранной мере (например, раньше заканчивается).
3. Перед доказательством поищи контрпример на маленьких данных.

Когда жадность ломается

Монеты 1, 3, 4, сумма 6: жадно 4 + 1 + 1, оптимум 3 + 3. Рюкзак 0/1: брать предметы по убыванию ценности на кг неверно (для дробного рюкзака верно). В таких задачах нужна динамика.

Сложность

Чаще всего O(n log n) из-за сортировки или O(n) одним проходом.

Ловушки

• Объявить жадность верной по паре примеров.
• Выбрать не тот ключ сортировки (по началу вместо конца).
• Не проверить равные значения при сортировке.

Что спросят на собесе

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