Задача "Картинная галерея"
В картинной галерее каждый сторож работает в течение некоторого
непрерывного отрезка времени. Расписанием сторожа называется множество пар
[T1(i), T2(i)] - моментов начала и конца дежурства i-го сторожа из интервала
[0; EndTime].
Для заданного расписания стражи требуется:
а) проверить, в любой ли момент времени в галерее находится не менее двух
сторожей. Если условие а) не выполняется, то:
б) перечислить все интервалы времени с недостаточной охраной (менее двух сторожей);
в) добавить наименьшее число сторожей с заданной, одинаковой для всех длительностью дежурства, чтобы получить правильное расписание (удовлетворяющее условию а));
г) проверить, можно ли обойтись без добавления новых сторожей, если разрешается сдвигать время дежурства каждого сторожа с сохранением времени его дежурства;
д) при положительном ответе на пункт г) составить расписание с наименьшим числом сдвигов.
Входные данные (все моменты времени задаются в целых минутах):
- EndTime - момент окончания стражи (момент начала - 0);
- N - число сторожей;
- T1(i), T2(i), i = 1,...,N - моменты начала и окончания дежурства i-го сторожа.
- Length - длительность дежурства каждого дополнительного сторожа.
Выходные данные:
- ответ на пункт а) в форме да/нет;
- при ответе "нет" на пункт а) - список пар (k,l) - начал и концов всех малоохраняемых интервалов с указанием числа сторожей в каждом (0 или 1);
- число дополнительных сторожей и моменты начала и окончания дежурства каждого дополнительного сторожа;
- ответ на пункт г) в форме да/нет; если "да", то номера сторожей, смена которых сдвигается, и значения сдвигов;
- ответ на пункт д) - наименьшее число сторожей, смена которых сдвигается, их номера и значения сдвигов.
Примечание. Программа должна допускать независимое тестирование пунктов
в), г), д).
