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

Что проверяют

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

Как отвечать

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

Каноничный пример это выбор максимального числа непересекающихся интервалов, где сортировка идёт по правому концу, а не по длине или началу.

Arrays.sort(v, Comparator.comparingInt(a -> a[1]));
int count = 0, last = Integer.MIN_VALUE;
for (int[] it : v) {
    if (it[0] >= last) { count++; last = it[1]; }
}

Стоимость обычно упирается в сортировку, то есть O(n log n), сам проход линейный. Из классики стоит назвать Краскала и Прима, Дейкстру на неотрицательных весах, коды Хаффмана и дробный рюкзак. Доказывают корректность аргументом замены: берём оптимальное решение и показываем, что первый жадный шаг можно в него внести, не ухудшив результат.

Где спотыкаются

Приводят размен монет как образцовый пример и не делают оговорку. Для номиналов 1, 3 и 4 на сумму 6 жадность даст 4 плюс 1 плюс 1, а оптимум это 3 плюс 3. Жадность здесь верна только для канонических систем номиналов, в общем случае задача решается динамикой.

Путают дробный рюкзак и рюкзак 0/1. Сортировка по удельной ценности оптимальна, только если предмет можно резать; при целых предметах тот же приём ломается на простом контрпримере, и нужна таблица.

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