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

Жадный алгоритм ~--- это общее название для целой группы разных алгоритмов. Все эти алгоритмы объединены естественным соображением пытаться как можно быстрее и проще получить ответ на задачу.

Антагонистом жадных алгоритмов является динамическое программирование. Там мы не можем заранее сказать, какой ход будет оптимальным, поэтому считаются все состояния динамики. Однако некоторые задачи можно решать как жадностью, так и динамикой. Разница будет только в асимптотике полученного алгоритма и в приложенных усилиях (жадники бывают очень нетривиальными). Пример такой задачи --- Региональный этап, первый тур, 4 февраля 2017г. задача 2 (Калькулятор).

Классическим примером задачи на жадность является задача о распределении времени. Допустим, у нас есть ряд лекций, все хотят попастать в аудиторию $X$. Каждый лектор может прочитать свою лекцию только в аудитории $X$, причем ровно во время с $l_i$ по $r_i$. Во имя всеобщего образования надо организовать порядок лекций так, чтобы было прочитано максимальное их число. Формально это можно понимать, как размещение максимального количества непересекающихся отрезков на прямой.

Как такое решать?

Правильным решением будет отсортировать отрезки по возрастанию правых концов. Пройдемся по отсортированному массиву отрезков, поддерживая самую правую правую (с отрезками всегда так) границу взятого отрезка, назовем ее $B$. Пусть сейчас рассматривается отрезок $[l, r]$. Если $B \le l$, то можно взять этот отрезок и обновить $B \leftarrow r$. Иначе продолжаем проход по массиву.

Почему это правильно

А теперь будет весьма абстрактненько. Пусть есть оптимальный алгоритм, назовем его OPT, и наш алгоритм, назовем его OUR. Нааш цель - показать, что OUT дает