Жадные алгоритмы

Жадный алгоритм на каждом шаге фиксирует локально лучший вариант и не пересматривает его. Это не эвристика «брать самое большое»: нужна доказуемая структура задачи.

Когда подход корректен

Обычно доказывают:

1. greedy-choice property — существует оптимальное решение, начинающееся с выбранного шага;
2. optimal substructure — остаток после шага является задачей того же вида;
3. exchange argument — любое оптимальное решение можно преобразовать так, чтобы его первый выбор совпал с жадным и результат не ухудшился.

Выбор непересекающихся интервалов

Чтобы выбрать максимум встреч, сортируем по времени окончания и берем ближайшую заканчивающуюся совместимую:

record Interval(int start, int end) {}
 
static List<Interval> select(List<Interval> input) {
    List<Interval> sorted = new ArrayList<>(input);
    sorted.sort(Comparator.comparingInt(Interval::end));
 
    List<Interval> result = new ArrayList<>();
    int lastEnd = Integer.MIN_VALUE;
    for (Interval interval : sorted) {
        if (interval.start() >= lastEnd) {
            result.add(interval);
            lastEnd = interval.end();
        }
    }
    return result;
}

Раннее окончание оставляет не меньше места для остальных интервалов. Сортировка O(n log n), проход O(n).

Дейкстра

Дейкстра жадно фиксирует непосещенную вершину с минимальной известной дистанцией. Корректность требует неотрицательных весов: отрицательное ребро может позже улучшить уже зафиксированный путь. С priority queue сложность обычно O((V + E) log V).

Алгоритм Флойда—Уоршелла решает другую задачу — пути между всеми парами — и относится к динамическому программированию, а не к greedy.

Контрпример: монеты

Для номиналов {1, 3, 4} и суммы 6 выбор крупнейшей монеты дает 4 + 1 + 1 — три монеты. Оптимум 3 + 3 — две. Значит правило, верное для некоторых денежных систем, не доказано для произвольных.

На собеседовании

• Достаточно ли локально лучшего выбора? Нет, нужна доказанная greedy-choice property.
• По какому ключу сортируют interval scheduling? По времени окончания.
• Можно ли Дейкстру с отрицательными ребрами? Нет.
• Как опровергнуть greedy? Найти минимальный контрпример.
• Чем отличается от dynamic programming? DP сравнивает/хранит альтернативные подзадачи, greedy фиксирует выбор.