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

Перед началом: динамическое программирование (модули 16–17), куча и top-K (модуль 9). Инструменты: Go 1.27, slices, sort, container/heap. Трудоёмкость: ~5 ч (теория 2 ч · практика 3 ч).

🔥 Инцидент: «Две встречи в одной переговорке в одно время»

Календарь бронирования проверял конфликт «наивно»: сравнивал новую встречу с последней добавленной. Пока брони шли по порядку, это работало. Но после переноса встреч список оказался не отсортирован — и система спокойно поставила две встречи в одну комнату в одно и то же время. Саппорт узнал об этом от двух команд, стоящих в дверях переговорки.

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

📖 Теория

18.1 Жадный выбор и обменный аргумент

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

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

Доказательство: пусть в оптимальном решении первым выбран интервал X, а жадный предпочёл J (у него окончание не позже). Заменим X на J: J заканчивается раньше, значит, не создаёт новых конфликтов с остальными выборами решения. Отсюда по индукции — жадное решение не хуже оптимального. Всего два предложения, но без них «жадный алгоритм» — это догадка, за которую на собеседовании снимают баллы.

18.2 Когда жадный ломается

Три классических контрпримера:

• Монеты [1, 3, 4], сумма 6. Жадный берёт 4, потом 1 и 1 — три монеты. Оптимум: 3 + 3 — две. Локально «жадно» — не глобально (модуль 16).
• 0/1-рюкзак. Жадный по «ценность/вес» ошибается: один тяжёлый предмет с лучшим соотношением может занять всю вместимость, а два средних дадут больше. Рюкзак — таблица (модуль 17).
• Дробный рюкзак (рвём предметы). А вот здесь жадный по «ценность/вес» оптимален: можно отсыпать половину, поэтому решение сводится к сортировке по соотношению.

Контраст поучителен: разница между работающим и неработающим жадным не в коде — в условиях задачи. Проверка: годится ли жадный — это либо доказательство (обменный аргумент), либо контрпример. Третьего нет.

18.3 Интервалы: сортировка по началу и по концу

Интервальные задачи решаются одной из двух сортировок, и выбор не случаен:

Слияние — проход с одним «текущим» интервалом: интервалы отсортированы по началу, поэтому новый либо пересекается с текущим, либо начинается после него. Минимум удалений — это §18.1 целиком: сортируем по окончанию и жадно берём всё, что не конфликтует.

go
// minRooms — сколько переговорок нужно: min-heap по временам окончания.
func minRooms(m [][2]int) int {
	sort.Slice(m, func(i, j int) bool { return m[i][0] < m[j][0] })
	h := &endHeap{}
	for _, iv := range m {
		if h.Len() > 0 && (*h)[0] <= iv[0] {
			heap.Pop(h) // ближайшая занятая комната освободилась
		}
		heap.Push(h, iv[1]) // встреча заняла комнату до iv[1]
	}
	return h.Len() // в куче — число одновременно занятых комнат в пике
}

Проверка корректности: в куче лежат времена окончания всех «открытых» встреч; если минимальный конец не позже нового начала — одна комната освободилась, можно переиспользовать. Размер кучи в максимуме и есть ответ.

18.4 Одномерные задачи: jump game и gas station

Пять минут обдумывания на бумаге — и здесь достаточно одного числа.

Jump game. Даны максимальные длины прыжков; дойти до конца? Жадное состояние — «самая дальняя достижимая позиция»:

go
reach := 0
for i, v := range jump {
	if i > reach {
		return false // позицию i не достать никаким способом
	}
	if i+v > reach {
		reach = i + v
	}
	if reach >= len(jump)-1 {
		return true
	}
}

Инвариант: после обработки i все позиции до reach достижимы. Ни таблиц, ни очередей — O(n) и O(1).

Gas station. Есть кольцевая трасса, на станции i дают gas[i] бензина и до следующей нужно cost[i]. Инвариант из двух частей: если сумма gas-cost по всему кругу отрицательна — решения нет; если на отрезке баланс ушёл в минус, старт не может лежать внутри этого отрезка — сдвигаем кандидата за место провала:

go
total, tank, start := 0, 0, 0
for i := range gas {
	diff := gas[i] - cost[i]
	total += diff
	tank += diff
	if tank < 0 { // здесь старт невозможен
		start = i + 1
		tank = 0
	}
}
// start — ответ, если total >= 0 (иначе решения нет)

18.5 Планировщики: почему «по концу» побеждает

Обобщение §18.1: когда спрашивают «максимум совместимых элементов по времени», сортировка по времени окончания почти всегда правильная. Причина в обменном аргументе: выбор, который освобождает ресурс раньше всех, оставляет максимум свободы для следующего выбора.

Отсюда же — планирование задач с дедлайнами (выбрать максимум задач к сроку), вариант с профитом (видоизменённый вариант с приоритетной очередью, модуль 9) и компиляторные «интервалы жизни регистров». Все они начинаются со слов «отсортируем по окончанию».

Практическое предупреждение: если задача формулируется через суммы, максимумы с выбором или состояние на каждом шаге — это, скорее всего, DP, а не жадный. Сигнал пожалеть: вспомните §18.2.

18.6 Компромиссы

💻 Практика

1. Merge и insert. Реализуйте merge([][2]int) (слияние пересекающихся) и insert(intervals, new) — вставку одного интервала со слиянием соседей. Тесты: пустой список, вложенные интервалы, касание границ ([1,3] и [3,5] — решите и зафиксируйте политику).
2. Минимум удалений. Найдите минимум интервалов, которые нужно убрать, чтобы оставшиеся не пересекались (жадный по концу). Отдельным тестом сравните с наивным перебором на 10 интервалах — ответы должны совпасть.
3. Переговорки. Минимальное число комнат через min-heap по концам. Тест: одна встреча, все встречи в один час, «ёлочка» без единого пересечения — ответ 1.
4. Jump game и gas station. Обе задачи на O(1) памяти. Тесты: прыжок невозможен ([3,2,1,0,4]), начинается на нуле, кольцо без газа (total < 0) — ответ −1.
5. Контрпример своими руками. Дополните сниппет мини-демонстрацией §18.2: сравните жадную сдачу и DP-оптимум на монетах [1, 3, 4] для сумм 1..15. Найдите первую сумму, где жадный проигрывает.

🧩 Quiz

✅ Итоги модуля

• Жадный алгоритм — не «взять побольше», а доказательство: обменный аргумент показывает, что локальный выбор не ухудшает оптимум.
• Контрпримеры держите в голове: монеты [1, 3, 4], 0/1-рюкзак, а дробный рюкзак — наоборот, решается жадным.
• Интервалы: слияние и вставка — сортировка по началу; максимум совместимых и минимум удалений — по концу; переговорки — куча по концам.
• Jump game и gas station — жадные в один проход с инвариантом, а не таблицей.

🔗 Мостик к Модулю 19

Остался последний «кирпич» базы, который прошивает всё предыдущее: биты и математика. В модуле 19 — «Биты и математика»: маски вместо 64 булевых полей, XOR-фокус с единственным числом, НОД и решето Эратосфена, быстрое возведение в степень по модулю и осторожность с переполнением int64 — инструменты, на которых стоят задачи про флаги, простые числа и криптографию по модулю.