Программирование. Задача о сторожах-2
 

Здравствуйте. В поисках решения своей задачи наткнулась на ваш форум – нашла решение другой задачи, похожей на часть моей -tehnari.ru/f41/t58807 , но целиком решить свою по-прежнему не могу, поэтому обращаюсь к вам за помощью.

Моя задача:

«В картинной галерее каждый сторож работает в течение некоторого непрерывного отрезка времени. Расписанием стражи называется множество пар [Т1(i), Т2(i)] - моментов начала и конца дежурства i-го сторожа из интервала [0,EndTime].

Для заданного расписания стражи требуется:

(а) проверить, в любой ли момент в галерее находится не менее двух сторожей.

Если условие (а) не выполнено, то:

(б) перечислить все интервалы времени с недостаточной охраной (менее 2 сторожей).

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

(г) проверить, можно ли обойтись без добавления новых сторожей, если разрешается сдвигать времена дежурства каждого из сторожей с сохранением длительности дежурства.

(д) Если это возможно, то составить расписание с наименьшим числом сдвигов.

ВХОДНЫЕ ДАННЫЕ:

(Все моменты времени задаются в целых минутах.)

EndTime - момент окончания стражи, т.е. охраняется отрезок времени [0, EndTime].

N -число сторожей.

T1[i], T2[i], i=1,..N - моменты начала и окончания дежурства i-го сторожа.

Length - длительность дежурства каждого дополнительного сторожа.

ВЫХОДНЫЕ ДАННЫЕ:

(1) Ответ на пункт (а) в форме да/нет.

(2) При ответе “нет” на п. (а) - список пар (k,l) - начал и концов всех малоохраняемых интервалов с указанием числа сторожей в каждом (0 или 1).

(3) Число дополнительных сторожей и моменты начала и окончания дежурства каждого дополнительного сторожа.

(4) Ответ на пункт (г) в форме да/нет. Если “да”, то номера сторожей, смена которых сдвигается, и значения сдвигов.

(5) В ответ на пункт (д): наименьшее число сторожей, смена которых сдвигается, их номера и значения сдвигов.

ПРИМЕЧАНИЕ

Программа должна допускать независимое тестирование пунктов (в), (г), (д).”»

Собственно, как ответить на пункты (а) и (б) я понимаю – пройтись в цикле по каждой минуте, считая количество сторожей, как предлагается в указанной выше теме, или еще можно для всех моментов начала/окончания дежурства (сначала создать из них массив и отсортировать его по возрастанию) получить ряд чисел, указывающих на то, как меняется количество стражей, например, +1, -1 (может быть и несколько), тогда суммируя эти числа можно будет получить количества стражей в каждый момент сдачи/приема дежурства и по ним найти интервалы с недостаточной охраной.

Я буду очень благодарна, если кто-нибудь поможет мне с пунктами (в), (г) и (д).

Что делать с пунктом (в) тоже более-менее понятно из единственного существующего пояснения к этой задаче:
“…Увеличение количества сторожей осуществляется последовательно. Вначале добавляются сторожа в интервалы времени с недостаточной охраной и отстоящие друг от друга на время, большее времени дежурства сторожей. После этого вновь выполняется сортировка и осуществляется поиск интервалов времени с недостаточной охраной. Если они есть, то процесс продолжается, и так до тех пор, пока в любой момент времени в галерее не будут находиться не менее двух сторожей.”
Правильно ли я понимаю, что на каждом шаге мы выбираем все интервалы, на которых 0 или 1 сторож (те, где 0, и те, где 1, рассматриваем отдельно) и время между которыми меньше заданного времени дежурства каждого доп. сторожа (пока возможно, на последнем шаге выбираем все оставшиеся интервалы с недостаточной охраной вне зависимости от времени между ними), и заполняем их до отказа, т.е. для тех, на которых 0, добавляем сразу двух? И если да, то можно ли как-то теоретически обосновать, что при таком подходе количество доп. сторожей будет минимальным?

Как делать пункты (г) и (д) я совсем не понимаю…Единственная зацепка в том, что во всех источниках, где встречается эта задача, она находится в разделе «графы». В одной книге перед ней даны описания алгоритмов расстановки пометок при поиске максимального потока и алгоритма Дейкстры, но я не представляю, к чему они тут. Нужно ли в этих пунктах использовать эти или, может быть, какие-то другие алгоритмы на графах, и если да, то какие и как?