Введение

Жадный алгоритм — это алгоритм, который на каждом шагу делает локально наилучший выбор в надежде, что итоговое решение будет оптимальным.

Сначала разберём базовые задачи, а затем осознаем всю мощь "жадных алгоритмов".

Задача об отрезках

Даны n отрезков. Отрезок задаётся двумя границами — началом и концом. Вам нужно выбрать как можно больше отрезков таким образом, чтобы ни один из них не пересекался с другим.

К решение проще приступить таким образом : нарисуйте n горизонтальных линей. Нарисуйте каждый отрезок на соответствующей прямой, просмотрите слева направо их. Когда вы выбираете какой-то отрезок, выделите его цветом, а все которые с ним пересекаются сотрите. Подумайте.

Возможно вы догадались до такой идеи — каждый раз брать отрезок у которого правая граница минимальная. Затем стирать все с ним пересекающиеся.

Это очевидно, по сути вы каждый раз выбираете отрезок, который стирает наименьшее количество отрезков. Но почему-бы не выбрать какой-то отрезок в центре?

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

Доказательство

Пусть наше жадное решение выбрало множество из k отрезков $A=\{(l_1,r_1),\dots ,(l_k,r_k)\}$, но на самом деле оптимальное решение выбрало m отрезков $B=\{(l_1,r_1),\dots ,(l_m,r_m)\}$.

Докажем, что $k=m$. По предположению выше $k\le m$.

Отсортируем все отрезки $A$ и $B$ по возрастанию правой границы, а в случае равенства по убыванию левой. Пусть $i$ первый индекс, где отрезки не совпадают ($A_i\ne B_i)$.

Пусть $i$ существует. Если нет, то прочтите текст в рамке второго случая.

Сравним $A_{i,r}$ и $B_{i,r}$.

1. Случай $A_{i,r}>B_{i,r}$ не возможен по определению нашего алгоритма.

2. Случай $A_{i,r}<B_{i,r}$.

Заметим, что замена $i$-го отрезка в $B$ на $A_i$ ничего не сломает, а возможно только увеличит количество взятых отрезков. Заменим отрезок. Заметим, что можно опять заменить другие отрезки, так как мы не ухудшаем ответ. Пришли к тому, что $i$ теперь не существует.

Первые $k$ отрезков в $B$ совпадают со всеми из $A$, а из этого следует, что $k=m$, так как в противном случае, жадное решение взяло бы ещё отрезки.

3. Случай $A_{i,r}=B_{i,r}$ возможен, но доказательство для левой границы аналогично.

Следовательно $k=m$ — корректность жадного решения доказана.

Общее доказательство для любых жадных алгоритмов аналогично.

Код :

void solve() {
  int n;
  cin >> n;
  vector<pair<int, int>> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i].first >> a[i].second;
  }
  sort(a.begin(), a.end(), [&](auto& x, auto& y) {
    return make_pair(x.second, -x.first) < make_pair(y.second, -y.first);
  });
  int ans = 0;
  int r = INT_MIN;
  for (int i = 0; i < n; i++) {
    if (r < a[i].first) {
      r = a[i].second;
      ans++;
    }
  }
  cout << ans;
}

Задачи на которых не работает

Задача о размене монет (это задача о рюкзаке)

Есть набор монет с разными номиналами, и вам нужно разменять заданную сумму минимальным количеством монет.

Например, в нашей выдуманной стране номиналы $3,5,10$. Разменять 5 можно одной 5, 13 на две 3 и 10 и тп.

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

НО, если у нас $1,9,10$ и нам надо разменять $18$, то оптимальнее начать не с $10$, а с $9$ (9 + 9 = 18).

Это задача имеет достаточно простое решение — динамическое программирование. Мы рассмотрим решение такой и подобных задач немного позже.