Мы используем необходимые куки для работы сайта (вход и язык). Если ты согласишься, мы также загрузим Google Analytics, чтобы видеть, какие страницы читают, и Google reCAPTCHA для защиты форм обратной связи и сообщений об ошибке от спама. Политика конфиденциальности

← Блог
Как готовиться

Жадный алгоритм: как узнать, что жадность верна, и три задачи с разбором

· 2026-11-10

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

Что такое жадный алгоритм?

Есть последовательность решений. На каждом шаге берём вариант, который выглядит лучше всего прямо сейчас. Назад не возвращаемся, перебора нет.

Такой подход быстрый и короткий в коде. Но верен он не всегда. Монеты [1, 3, 4] и сумма 6 ломают жадность. Она берёт 4, 1, 1 вместо 3, 3.

Поэтому главный вопрос про жадный алгоритм всегда один. Почему локальный выбор не портит глобальный ответ?

Жадно набрать 18 наименьшим числом монет
minCoinsGreedy([1, 5, 2, 10], 18)
coins
1
5
2
10
amount = 18
used
пусто

Нужно набрать 18 как можно меньшим числом монет. Жадное правило: всегда брать самую крупную монету, которая ещё помещается.

Гонка скорости
Перебор всех подмножеств и жадный выбор на одних и тех же 11 встречах: как уместить больше всего встреч без наложений

Столбики: когда заканчивается каждая встреча, в порядке их начала.

Одна операция: одна проверка встречи или одно сравнение при сортировке. За каждый кадр все дорожки делают одинаковое число операций, поэтому медленная отстаёт.

Перебор всех подмножеств O(2ⁿ·n)
операций: 0
Жадный выбор по времени окончания O(n log n)
операций: 0

 

А если чисел больше

Операции для n чисел и примерное время при 100 миллионах простых операций в секунду. Это оценка по тому же счёту, а не замер.

n = 10
Перебор всех подмножеств2,2 тыс. · меньше 1 мс
Жадный выбор по времени окончания33,3 · меньше 1 мс
n = 20
Перебор всех подмножеств2,2 млн · 22 мс
Жадный выбор по времени окончания80,5 · меньше 1 мс
n = 40
Перебор всех подмножеств2,3 трлн · 6,4 ч
Жадный выбор по времени окончания189 · меньше 1 мс

Страница паттерна: когда его применять и шаблон на шести языках

Как проверить, что жадный алгоритм верен?

Обменный аргумент. Берём любое оптимальное решение. Показываем, что первый его шаг можно заменить на жадный. Решение не станет хуже. Повторяем для каждого шага. Значит жадное решение не хуже оптимального.

На собеседовании полное доказательство не пишут. Достаточно назвать обмен и сказать, почему он ничего не ломает.

Второй способ: попытаться придумать контрпример. Не нашли за минуту, вероятно жадность верна. Нашли, нужно динамическое программирование.

По каким словам в задаче узнать жадный алгоритм?

  • «Максимальное число непересекающихся отрезков».
  • «Минимальное число прыжков», «минимальное число заправок».
  • «Раздать печенье», «назначить задачи» с одним критерием.
  • «Можно ли дойти до конца», «минимальное число стрел».

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

Как это выглядит на примере?

Задача о выборе заявок. Отрезки [1, 4], [3, 5], [0, 6], потом [5, 7] и [8, 9]. Нужно максимум непересекающихся. Сортируем по концу, порядок остаётся тем же.

Берём [1, 4], конец 4. [3, 5] начинается раньше 4, пропускаем. [0, 6] пропускаем. [5, 7] начинается в 5, берём, конец 7. [8, 9] берём. Ответ 3.

Обмен: любое оптимальное решение можно начать с отрезка, который кончается раньше всех. Он освобождает больше места для остальных.

Как написать жадный алгоритм на Python?

def max_non_overlapping(intervals):
    intervals.sort(key=lambda x: x[1])      # по концу
    count, end = 0, float("-inf")
    for s, e in intervals:
        if s >= end:
            count += 1
            end = e
    return count

def can_jump(nums):
    reach = 0
    for i, step in enumerate(nums):
        if i > reach:
            return False                    # сюда не дойти
        reach = max(reach, i + step)
    return True

def min_jumps(nums):
    jumps = cur_end = farthest = 0
    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        if i == cur_end:                    # край текущего прыжка
            jumps += 1
            cur_end = farthest
    return jumps

def assign_cookies(children, cookies):
    children.sort(); cookies.sort()
    i = j = 0
    while i < len(children) and j < len(cookies):
        if cookies[j] >= children[i]:
            i += 1                          # ребёнок доволен
        j += 1
    return i

Во всех четырёх функциях один проход после сортировки или без неё. В этом сила приёма.

Чем жадный алгоритм отличается от соседних приёмов?

ПриёмКак выбираетКогда веренВремя
Жадный алгоритмЛучший локальный шаг без откатаЕсть обменный аргументO(n log n)
Динамическое программированиеПеребирает состояния, помнит ответыВсегда, если состояние заданоO(n · состояния)
БэктрекингПеребирает с откатомВсегда, но экспонентаO(2ⁿ) и хуже
Бинарный поиск по ответуПроверяет догадкуПроверка монотоннаO(n log R)

Как решить Jump Game?

Массив прыжков, из позиции i можно прыгнуть на nums[i] вперёд. Дойдём ли до конца? Держим самую дальнюю достижимую позицию. Идём слева направо. Позиция дальше достижимой, ответ нет. Иначе обновляем максимум.

Обмен: не важно, откуда мы дошли до позиции i. Важно только, что дошли. Поэтому хватает одного числа.

Как решить Gas Station?

Кольцо заправок, на каждой есть бензин и расход до следующей. Откуда стартовать, чтобы проехать круг? Если суммарного бензина меньше суммарного расхода, ответа нет. Иначе идём по кругу с баком. Бак ушёл в минус, старт переносим на следующую заправку и обнуляем бак.

Обмен: из старта s не доехать до i. Тогда из любой заправки между ними тоже не доехать. Их можно пропустить сразу.

На каких ошибках ломается жадный алгоритм?

  • Сортируют по началу вместо конца в задаче о заявках. Длинный ранний отрезок съедает всё.
  • Применяют жадность к монетам произвольных номиналов.
  • Не проверяют суммарный баланс в Gas Station и зацикливаются.
  • Берут жадность там, где два критерия спорят. Нужно DP.

Как объяснить жадный алгоритм на собеседовании?

Назовите правило выбора одной фразой. Потом сразу обменный аргумент. Почему замена любого шага на жадный не портит ответ. Потом код.

Если сомневаетесь, скажите это вслух. «Проверю жадность на контрпримере» звучит лучше, чем неверный ответ с уверенным видом.

Отработать узнавание приёма можно на странице жадный алгоритм. Задачи на отрезки разобраны на странице интервалы.

Вопросы и ответы

Почему жадность работает для монет 1, 5, 10, 25?

Номиналы устроены так, что большая монета всегда выгоднее набора мелких. Для 1, 3, 4 это не так. Свойство называют каноническим набором монет.

Как понять, жадность или DP?

Попробуйте сломать жадность маленьким примером за минуту. Не получилось, ищите обменный аргумент. Получилось, пишите таблицу.

Алгоритм Дейкстры жадный?

Да. Он берёт ближайшую вершину и не возвращается к ней. Обменный аргумент: при неотрицательных весах обходной путь не бывает короче.

Где жадный алгоритм встречается в реальных системах?

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