Екзаменаційна сесія#13106

Екзаменаційна сесія (Розбір)

Пройдемо дні за зростанням і для кожного дня вирішимо, який іспит скласти в цей день. Жадібний алгоритм (спершу найближчий дедлайн): серед іспитів, які ще не складено і вікно яких уже відкрилося (l_i \le d, де — поточний день), беремо той, у якого r_i найменше. Якщо це r_i < d, відповідь NO; якщо кожен іспит отримав день, відповідь YES.

Чому це правильно. Нехай деякий допустимий вибір днів збігається з жадібним на всіх днях до , і нехай — іспит, обраний у день . У цьому виборі x_e \ge d: кожен попередній день зайнятий іншим іспитом або був пропущений, коли всі l_i решти іспитів були більшими. Отже, r_e \ge x_e \ge d, і в день жадібний алгоритм не відповідає NO. Якщо день у цьому виборі вільний, перенесемо на день . Якщо день зайнятий іншим іспитом , поміняємо їх: переходить на день , а — на день x_e, і це можна, бо l_f \le d < x_e \le r_e \le r_f (жадібний алгоритм обрав , тож r_e \le r_f). В обох випадках вибір лишається допустимим і тепер збігається з жадібним і в день . За індукцією, якщо допустимий вибір існує, жадібний алгоритм ніколи не відповідає NO; а якщо він відповідає YES, то обрані ним дні і є допустимим вибором.

Реалізація. Відсортуємо іспити за l_i і зберігатимемо відкриті в мін-купі за r_i. Дні сягають 10^9, тому не перебираємо їх по одному: коли купа порожня, одразу переходимо до наступного l_i. Кожен крок циклу виймає з купи один іспит, тож кроків рівно .

Той самий критерій можна сформулювати через теорему Голла: відповідь YES тоді й лише тоді, коли кожен відрізок днів містить не більше ніж b - a + 1 вікон [l_i, r_i] цілком. Жадібний алгоритм перевіряє це неявно.

Складність — O(n \log n) на тестовий випадок.