Greedy

Greedy-алгоритмы основаны на простой философии: на каждом шаге делай локально оптимальный выбор и надейся, что это приведёт к глобальному оптимуму. Звучит заманчиво, но здесь кроется главная ловушка — greedy работает только для специальных классов задач, где «локальная жадность» не закрывает будущие возможности. Представьте, что вы идёте к вершине горы и на каждом шаге двигаетесь в направлении максимального подъёма: для выпуклой горы это сработает, но если есть локальные максимумы — застрянете не на самой высокой вершине. С алгоритмами всё аналогично.

Когда применять

Greedy применим, если задача обладает двумя свойствами:

Greedy choice property — локально оптимальный выбор не закрывает доступ к глобальному оптимуму.
Optimal substructure — оптимальное решение состоит из оптимальных решений подзадач (это же свойство нужно и для DP).

Хорошие сигналы того, что задача жадная:

Задачи с матроидной структурой (Activity Selection, MST через Kruskal/Prim).
Задачи, где «выбор не закрывает будущее» (Dijkstra при неотрицательных весах: выбранная вершина уже финализирована).
Задачи с монотонностью (Huffman codes — всегда объединяем два минимальных).
Задачи на интервалы: Interval Scheduling, Meeting Rooms, Merge Intervals, Jump Game.

Идея

Классический пример, где greedy работает идеально, — Activity Selection (выбор максимального числа непересекающихся интервалов). Секрет в том, чтобы сортировать интервалы по времени окончания и жадно брать первый доступный. Почему это оптимально? Взяв интервал с минимальным концом, мы оставляем максимум возможностей для будущих выборов.

Это можно доказать через exchange argument: пусть есть оптимальное решение, где первый интервал — не наш (с минимальным концом). Заменим его на наш — все последующие интервалы в оптимуме остаются валидными (наш кончается раньше или одновременно), значит, наше решение тоже оптимально.

А вот контрпример — 0/1 Knapsack. Если жадно брать предметы по убыванию value/weight, можно промахнуться. Возьмём предметы {(w=10,v=60), (w=20,v=100), (w=30,v=120)} и рюкзак W=50. Greedy по плотности: (10,60) — плотность 6, потом (20,100) — плотность 5, итого weight=30, value=160. Но оптимум: взять (20,100) и (30,120) — value=220! Greedy провалился. Для 0/1 Knapsack нужна динамика. А вот для fractional knapsack (можно брать дробные части) greedy по плотности работает идеально.

Реализация

Разберём задачу Jump Game II: дан массив неотрицательных целых nums, где nums[i] — максимальная длина прыжка из позиции i. Стартуем в nums[0], нужно достичь последнего индекса за минимальное количество прыжков. Гарантируется, что цель достижима. Пример: [2,3,1,1,4] → 2 прыжка (0→1→4).

Жадный подход: на каждом шаге стремимся прыгнуть как можно дальше «в пределах текущего прыжка». Пока идём от текущей позиции до конца текущего прыжка, отслеживаем максимальную дальность, которую можем достичь из любой точки этого диапазона. Когда достигаем конца — делаем следующий прыжок (инкрементируем счётчик) и обновляем границу до найденной максимальной дальности.

function jump(nums: number[]): number {
  if (nums.length <= 1) return 0;

  let jumps = 0;
  let currentEnd = 0;   // конец текущего прыжка
  let farthest = 0;     // максимальная дальность в пределах текущего прыжка

  for (let i = 0; i < nums.length - 1; i++) {
    farthest = Math.max(farthest, i + nums[i]);

    if (i === currentEnd) {
      jumps++;
      currentEnd = farthest;
      if (currentEnd >= nums.length - 1) break; // достигли конца
    }
  }

  return jumps;
}

console.log(jump([2, 3, 1, 1, 4])); // 2
console.log(jump([2, 3, 0, 1, 4])); // 2 (0→1→4, минуя ловушку)

Трассировка

Прогоним для [2,3,1,1,4]:

i=0: farthest=max(0, 0+2)=2, i=currentEnd=0 → jumps=1, currentEnd=2
i=1: farthest=max(2, 1+3)=4, i ≠ currentEnd
i=2: farthest=max(4, 2+1)=4, i=currentEnd=2 → jumps=2, currentEnd=4 → break
Ответ: 2 прыжка

Почему это работает: мы никогда не «пропускаем» лучший вариант, потому что на каждом этапе рассматриваем ВСЕ позиции в пределах текущего прыжка и выбираем максимальную дальность из них. Это гарантирует минимальное число прыжков, так как мы максимизируем покрытие на каждом шаге.

Сложность

Время: O(n) — один проход, каждый индекс обрабатывается ровно раз.
Память: O(1) — только переменные.

В целом большинство greedy-алгоритмов имеют сложность O(n log n) из-за сортировки и O(n) на сам жадный проход. Это оптимально, так как обычно нужно хотя бы просмотреть весь вход.

Когда greedy НЕ работает

:::caution Coin Change с неканоническими номиналами Монеты {1, 3, 4}, сумма 6. Greedy берёт 4, остаётся 2 → 1+1, итого 3 монеты. Оптимум: 3+3 — 2 монеты. Здесь нужна DP. :::

Другой пример — 0/1 Knapsack: greedy по плотности (value/weight) не гарантирует оптимум, нужна DP O(nW). Правило простое: если «жадный выбор» может заблокировать лучший будущий вариант, greedy провалится.

Типичные ошибки и подводные камни

Неправильная сортировка — например, сортировать интервалы по началу, а не по концу.
Забыть проверить feasibility — можно ли вообще применить выбор.
Не учитывать граничные случаи — пустые входы, одинаковые элементы, нулевые длины.
Перепутать матроидные и не матроидные задачи — coin change vs canonical coin systems.

Edge cases: все интервалы пересекаются (ответ 1), все не пересекаются (ответ n), нулевые длины, одинаковые приоритеты.

Применения

Scheduling: распределение задач по машинам, выбор непересекающихся встреч.
Coin Change для канонических систем (1, 5, 10, 25 — greedy работает).
MST: Kruskal жадно берёт минимальное ребро, не создающее цикл.
Huffman codes: жадно объединяем два минимальных по частоте узла.
Dijkstra: жадно берём ближайшую непосещённую вершину.

Follow-up вопросы

Почему для Activity Selection сортировка по времени окончания работает, а по началу — нет? Сортировка по началу может дать длинный интервал первым, который перекрывает много коротких. Контрпример: [(1,10), (2,3), (4,5)] — по началу берём (1,10), ответ 1; по концу: (2,3), (4,5), ответ 2. Сортировка по концу гарантирует, что взятый интервал освобождает будущее максимально рано.
Можно ли применить greedy к Longest Increasing Subsequence? Нет напрямую. Если жадно брать каждый элемент больше предыдущего, пропустим более длинные subsequence с меньшими элементами. Пример: [3,1,2,4] — жадно берём 3,4 (длина 2), а LIS: 1,2,4 (длина 3). Нужен DP O(n²) или O(n log n) с patience sorting.
Как доказать корректность greedy через exchange argument? Возьмём любое оптимальное решение OPT. Если первый выбор OPT отличается от greedy, покажем, что можем заменить его на greedy-выбор без ухудшения. Продолжаем заменять, пока не получим greedy-решение. Если оно оптимально — доказано. Пример: MST Kruskal — если оптимум содержит более тяжёлое ребро вместо лёгкого, заменяем (не создаём цикл, так как оптимум тоже дерево).
Задача Gas Station: как greedy решает? Даны станции с газом gas[i] и стоимостью перехода cost[i]. Greedy: накапливаем баланс gas-cost. Если баланс отрицательный — не можем стартовать отсюда и раньше → двигаем старт на следующий индекс. Если полный баланс ≥ 0, решение есть. O(n).
Почему Dijkstra — это greedy, и когда он ломается? Dijkstra жадно выбирает ближайшую непосещённую вершину и финализирует её расстояние. Это работает при неотрицательных весах: любой другой путь через непосещённые будет не короче. При отрицательных весах можем найти более короткий путь позже через отрицательное ребро → нужен Bellman-Ford.
Fractional vs 0/1 Knapsack: почему для первого greedy работает? Fractional: можем взять часть предмета. Greedy по плотности оптимален, так как каждая единица веса добавляет максимально возможную ценность. 0/1: предметы целиком — взяв высокоплотный тяжёлый предмет, можем потерять комбинацию лёгких с большей суммарной ценностью.

Чеклист на собес

Сформулируй greedy choice вслух.
Попробуй построить контрпример. Если не нашёл — попробуй доказать exchange argument.
Проверь edge cases: пустой вход, n=1, все равны, отрицательные значения.
Назови сложность: обычно O(n log n) (сортировка) + O(n) (проход).
Если не уверен в корректности — упомяни DP как запасной вариант.