---
title: "Жадный алгоритм (обменный аргумент)"
url: https://algopath.pro/ru/patterns/greedy
language: ru
summary: "Берите лучший на вид вариант прямо сейчас и никогда к нему не возвращайтесь. Работает это, только если есть доказательство."
updated: 2026-08-24
---

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

Берите лучший на вид вариант прямо сейчас и никогда к нему не возвращайтесь. Работает это, только если есть доказательство.

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

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

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

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

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

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

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

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

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

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

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

- **Динамическое программирование (1-D)** - Динамика держит все варианты открытыми до конца. Жадность выбирает сразу и не может откатиться.
- **Бэктрекинг** - Бэктрекинг пробует все варианты и оставляет лучший. Жадность пробует один и ему верит.
- **Сортировка с пользовательским компаратором** - Большинство жадных решений начинается с сортировки. В компараторе и записан сам выбор.
- **Бинарный поиск по ответу** - Там сама проверка часто жадная. Поиск лишь выбирает значение для проверки.

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

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

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

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

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

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

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

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

```javascript
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;
}
```

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

- **Пропускают доказательство** Жадное правило, звучащее верно, очень часто неверно. Сначала поищите контрпример.
- **Сортируют не по тому ключу** Ранний старт и ранний конец дают разные ответы. Ключ выбирает доказательство, а не интуиция.
- **Берут жадность там, где выборы связаны** Размен монет со странными номиналами её ломает. Там безопасен только динамический подход.
- **Пытаются отменить выбор** Как только жадность что-то забирает назад, это уже перебор. Пишите бэктрекинг или динамику.

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

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

## JavaScript

```javascript
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;
}
```

## Python

```python
def min_coins_greedy(coins, amount):
    used = []
    for coin in sorted(coins, reverse=True):
        while amount >= coin:
            amount -= coin
            used.append(coin)
    return used if amount == 0 else None
```

## PHP

```php
function minCoinsGreedy(array $coins, int $amount): ?array {
    rsort($coins);
    $used = [];
    foreach ($coins as $coin) {
        while ($amount >= $coin) {
            $amount -= $coin;
            $used[] = $coin;
        }
    }
    return $amount === 0 ? $used : null;
}
```