Жадность с кучей

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

Тогда к сортировке добавляется очередь с приоритетом.

Дедлайны с отказом от худшего

Есть $n$ работ. Работа $i$ приносит прибыль $p_i$ и должна быть выполнена не позже дня $d_i$. За день делается одна работа. Максимизировать прибыль.

Первая мысль — сортировать по прибыли и брать жадно. Работает, но требует поиска свободного дня и системы непересекающихся множеств.

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

sort(jobs.begin(), jobs.end());   // по дедлайну
priority_queue<long long, vector<long long>, greater<long long>> taken;
long long total = 0;
for (const auto& [deadline, profit] : jobs) {
    taken.push(profit);
    total += profit;
    if ((int)taken.size() > deadline) {   // не помещаемся — выкидываем худшую
        total -= taken.top();
        taken.pop();
    }
}

Куча минимума — ключевая деталь: выбрасывать надо наименее прибыльную из уже взятых, а не текущую.

Почему верно: набор из $k$ работ выполним тогда и только тогда, когда при сортировке по дедлайну $i$-я по счёту имеет дедлайн не меньше $i$. Алгоритм поддерживает это как инвариант, а при нарушении жертвует наименьшей потерей.

Проверено перебором всех подмножеств: на двадцати тысячах случайных наборов до семи работ ответы совпали.

Сложность — $O(n \log n)$.

Слияние файлов

Есть $n$ файлов размерами $a_i$. За одну операцию два файла склеиваются, и это стоит суммы их размеров. Склеить всё в один за минимальную стоимость.

Жадность: каждый раз склеивать два наименьших.

priority_queue<long long, vector<long long>, greater<long long>> pq(a.begin(), a.end());
long long total = 0;
while (pq.size() > 1) {
    long long x = pq.top(); pq.pop();
    long long y = pq.top(); pq.pop();
    total += x + y;
    pq.push(x + y);
}

Проверено полным перебором порядков склейки на трёх тысячах наборов до шести файлов — расхождений нет.

Почему верно, видно, если посмотреть иначе: файл участвует в стоимости столько раз, какова его глубина в дереве склеек. Значит, минимизируется $\sum a_i \cdot depth_i$ — и большие файлы должны быть ближе к корню. Ровно это и делает алгоритм, отправляя маленькие вниз первыми.

Это алгоритм Хаффмана, тот самый, что лежит в основе сжатия данных. Задача про файлы и задача про оптимальный префиксный код — одна и та же задача.

Минимум аудиторий

Даны $n$ занятий с интервалами $[l_i, r_i)$. Сколько нужно аудиторий, чтобы провести все?

Ответ — максимальное число одновременно идущих занятий. Считается сканированием событий:

vector<pair<int, int>> events;
for (const auto& [l, r] : lessons) {
    events.push_back({l, +1});
    events.push_back({r, -1});
}
sort(events.begin(), events.end());

int current = 0, answer = 0;
for (const auto& [time, delta] : events) {
    current += delta;
    answer = max(answer, current);
}

Тонкость в сортировке: при равном времени событие $-1$ должно идти раньше $+1$, иначе занятие, кончающееся ровно тогда, когда другое начинается, посчитается пересечением. Пара {time, delta} сортируется правильно сама собой — $-1 < +1$.

Проверено против прямого подсчёта по всем моментам времени на двадцати тысячах наборов.

Если помимо количества нужно распределение занятий по аудиториям, кучу заводят из времён освобождения: берём занятия по возрастанию начала, и если самая рано освобождающаяся аудитория уже свободна — сажаем туда, иначе открываем новую.

Общая форма

Все три задачи устроены одинаково:

1. отсортировать по «времени» (дедлайн, начало, размер);
2. идти по порядку, поддерживая кучу уже принятых решений;
3. на каждом шаге либо добавлять, либо отменять худшее из накопленного.

Признак, по которому такая задача узнаётся: решение о взятии элемента можно пересмотреть позже. Если пересматривать нечего, хватит сортировки; если пересмотр зависит от всей истории, а не от одного худшего элемента, — скорее всего, нужна динамика.

И практическое: priority_queue по умолчанию выдаёт максимум. В большинстве этих задач нужен минимум, то есть priority_queue<T, vector<T>, greater<T>>. Забытый greater — самая частая ошибка в таких решениях, и находится она мгновенно, потому что ответ получается абсурдным на первом же тесте.