Библиотека

Первоначально преобразуем данные о каждой книги в отрезки дней, в каждый из которых книга уже может быть сдана, то есть отрезки books вида [si + ci, fi] — от момента прочтения книги до дня, по прошествии которого книга должна быть сдана. Затем отсортируем все отрезки по левому концу.

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

Реализовывать будем следующим образом. Каждый правый конец отрезка по мере возможности сдачи соответствующей ему книги в текущий день будем добавлять в множество. Текущий день храним в переменной j, еще не рассмотренный отрезок - в переменной i. Первоначально j соответствует минимальному левому концу среди левых концов всех отрезков. На каждой итерации цикла сначала добавляем все доступные для сдачи в текущий день j книги (увеличивая при этом переменную i), а затем вынимаем из множества минимальный правый конец среди всех правых концов доступных книг. И если вынутый правый конец оказался меньше j, то есть текущего свободного дня, выводим NO и завершаем программу.

Иначе идем дальше. Если после извлечения элемента множество оказалось пусто, присваиваем переменной j значение левого конца еще не рассмотренного отрезка, то есть j = books[i].left. В ином случае, если множество не оказалось пустым, увеличиваем j на один. Затем переходим к следующей итерации.

После цикла выводим YES.