Разбор задачи «Фестиваль премьер»

Идея задачи

Для каждого фильма известны два возможных дня показа:

• a_i — день, который указан в официальной афише;
• b_i — более ранний день, в который фильм тоже можно показать.

Для каждого фильма нужно выбрать один из этих двух дней так, чтобы:

1. фактические дни показов шли в неубывающем порядке;
2. день последнего показа был как можно меньше.

Это классическая задача на жадный алгоритм после сортировки.

Ключевое наблюдение

Порядок фильмов определяется значениями a_i. Значит, сначала нужно отсортировать все пары (a_i, b_i) по a_i.

После этого мы будем идти слева направо и поддерживать:

• last — день, в который мы назначили предыдущий фильм.

Для текущего фильма есть два варианта:

• выбрать b_i, если это не нарушает порядок, то есть если b_i >= last;
• иначе выбрать a_i.

Почему выгодно брать b_i, когда это возможно? Потому что b_i <= a_i, а значит b_i не хуже, а обычно лучше: он делает текущий день показа меньше и оставляет больше свободы для следующих фильмов.

Почему жадный алгоритм корректен

Рассмотрим очередной фильм после сортировки по a_i.

К этому моменту все предыдущие решения уже зафиксировали минимально возможный день last для последнего из рассмотренных фильмов.

Для текущего фильма:

• если b_i >= last, то можно поставить его в день b_i;
• если вместо этого поставить его в a_i, то день будет не меньше, а значит это решение не дает никакой выгоды;
• если b_i < last, то ставить фильм в b_i уже нельзя, потому что нарушится неубывание;
• тогда остается только a_i.

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

• берем b_i, если можно;
• иначе берем a_i.

Такой локально оптимальный выбор ведет и к глобально оптимальному ответу.

Алгоритм

1. Считать n и все пары (a_i, b_i).
2. Отсортировать пары по a_i.
3. Завести переменную last = 0.

4. Для каждой пары:

   • если b_i >= last, то last = b_i;
   • иначе last = a_i.
5. После обработки всех фильмов вывести last.

Пример работы

Пусть после сортировки получили:

(1, 1)
(2, 1)
(2, 2)
(4, 3)

Идем по порядку.

Первый фильм

• last = 0
• b = 1 >= 0, можно выбрать 1
• теперь last = 1

Второй фильм

• b = 1 >= 1, снова можно выбрать 1
• теперь last = 1

Третий фильм

• b = 2 >= 1, выбираем 2
• теперь last = 2

Четвертый фильм

• b = 3 >= 2, выбираем 3
• теперь last = 3

Ответ: 3.

Сложность

Сортировка занимает O(n log n).

Один проход по массиву после сортировки — O(n).

Итоговая сложность:

O(n log n)

Память:

O(n)

Типичные ошибки

1. Сортировать по b_i

Это неверно. Порядок объектов задается именно значениями a_i, а не b_i.

2. Всегда выбирать минимальное из a_i и b_i

Так можно нарушить неубывание фактических дней.

3. Пытаться применять сложное динамическое программирование

Здесь достаточно простой жадности: для текущего фильма нужно выбрать как можно более ранний допустимый день.

Реализация на C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<pair<int, int>> films(n);
    for (int i = 0; i < n; i++) {
        cin >> films[i].first >> films[i].second;
    }

    sort(films.begin(), films.end());

    int last = 0;
    for (int i = 0; i < n; i++) {
        int a = films[i].first;
        int b = films[i].second;

        if (b >= last) {
            last = b;
        } else {
            last = a;
        }
    }

    cout << last << '\n';
    return 0;
}

Реализация на Python

n = int(input())
films = []

for _ in range(n):
    a, b = map(int, input().split())
    films.append((a, b))

films.sort()

last = 0

for a, b in films:
    if b >= last:
        last = b
    else:
        last = a

print(last)

Почему решение получается таким коротким

Хотя формулировка кажется запутанной, после сортировки у каждого фильма остается очень простой выбор:

• либо более ранний день b_i, если он еще допустим;
• либо день a_i, если более ранний уже использовать нельзя.

Именно поэтому вся задача сводится к одной сортировке и одному линейному проходу.

Вывод

В этой задаче важно заметить две вещи:

1. сначала нужно упорядочить фильмы по a_i;
2. затем всегда выгодно брать минимально возможный допустимый день.

Это и приводит к аккуратному жадному решению за O(n log n).