Задача розв'язується прямим моделюванням: достатньо в кожен момент часу знати, чи є конкретна книжка в бібліотеці.
Заведемо булевий масив , у якому означає, що книжка зараз наявна. Початково всі книжки на місці, тому масив заповнюємо значенням «так».
Далі обробляємо відвідувачів по порядку:
t = 1 (хоче взяти книжку ): якщо істинне, відвідувач забирає книжку і ми ставимо у «ні». Інакше книжки немає — збільшуємо лічильник невдоволених;
t = 2 (повертає книжку ): ставимо у «так».
Відповідь — значення лічильника після обробки всіх запитів.
Умова гарантує, що повертають лише раніше взяту книжку, тому додаткових перевірок для t = 2 не потрібно. Важливо, що кожна книжка існує в єдиному екземплярі, — саме тому вистачає булевого прапорця, а не лічильника.
Складність — \mathcal{O}(n + m), що при n \le 1000 і m \le 5000 працює миттєво.