Жадный алгоритм (обменный аргумент)

Жадный алгоритм (обменный аргумент): как это работает?

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

Отсортируйте вход так, чтобы этот вариант был впереди. Сортировка и есть основная работа.

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

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

Доказывают это обменом: возьмите любой оптимальный ответ и подставьте свой выбор. Если он остался оптимальным, жадность безопасна.

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

1. по концу: [1,3], [2,4], [3,5]Бронируем встречи. Впереди та, что кончается раньше.
2. берём [1, 3]Она кончается раньше всех и оставляет больше места.
3. пропускаем [2, 4]Она начинается в 2, до конца предыдущей.
4. берём [3, 5]Она начинается ровно тогда, когда комната освободилась.
5. ответ = 2Помещаются две встречи. Сортировка по длине могла бы потерять одну.

function minCoinsGreedy(coins, amount) {
    const sorted = [...coins].sort((a, b) => b - a);
    const used = [];
    for (const coin of sorted) {
        while (amount >= coin) {
            amount -= coin;
            used.push(coin);
        }
    }
    return amount === 0 ? used : null;
}

Жадный алгоритм (обменный аргумент): разбор примера

Наименьшее число стрел для шаров

Шары занимают горизонтальные отрезки. Стрела, выпущенная в точке x, лопает все шары, накрывающие x.

Верните наименьшее число стрел, лопающих все шары.

Отсортируйте шары по правому краю.

Стреляйте в первый правый край и пропускайте все накрытые шары. Потом стреляйте в следующий не накрытый край.

function findMinArrowShots(points) {
    points.sort((a, b) => a[1] - b[1]); // by right edge, never by left

    let arrows = 1;
    let shot = points[0][1]; // the earliest right edge

    for (const [start, end] of points) {
        if (start > shot) {
            arrows++;
            shot = end; // this balloon is out of reach of the last arrow
        }
    }

    return arrows;
}

Жадный алгоритм (обменный аргумент): когда применять?

Эти формулировки в условии ведут сюда:

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

Жадный алгоритм (обменный аргумент): с чем путают?

• Динамическое программирование (1-D) (Dynamic programming (1-D)): Динамика держит все варианты открытыми до конца. Жадность выбирает сразу и не может откатиться.
• Бэктрекинг (Backtracking): Бэктрекинг пробует все варианты и оставляет лучший. Жадность пробует один и ему верит.
• Сортировка с пользовательским компаратором (Sort with a custom comparator): Большинство жадных решений начинается с сортировки. В компараторе и записан сам выбор.
• Бинарный поиск по ответу (Binary search on the answer): Там сама проверка часто жадная. Поиск лишь выбирает значение для проверки.

Жадный алгоритм (обменный аргумент): частые ошибки

• Пропускают доказательство

  Жадное правило, звучащее верно, очень часто неверно. Сначала поищите контрпример.

• Сортируют не по тому ключу

  Ранний старт и ранний конец дают разные ответы. Ключ выбирает доказательство, а не интуиция.

• Берут жадность там, где выборы связаны

  Размен монет со странными номиналами её ломает. Там безопасен только динамический подход.

• Пытаются отменить выбор

  Как только жадность что-то забирает назад, это уже перебор. Пишите бэктрекинг или динамику.

Жадный алгоритм (обменный аргумент): задачи с собеседований

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

Жадный алгоритм (обменный аргумент): сложность по времени и памяти

O(n log n)

Обычно O(n log n), и всё это сортировка. Проход после неё это один цикл.