6031. Бронирование

У Пьера сегодня большие проблемы! Он отвечает за управление бронирования номеров для РУЦ (Размещение по Умеренной Цене) отеля и буквально недавно понял, что программное обеспечение бронирования содержит серьезный баг. Это создало прецедент перекрывания и неправильного назначения номеров. Пьер очень обеспокоен тем, что отель может быть перебронирован. Поскольку производитель программного обеспечения не является ни отзывчивым, ни компетентным человеком, то Пьер должен делать все сам, своевременно принимая контрмеры в случае необходимости.

К счастью, Пьер был в состоянии экспортировать все оригинальные заказы (в том числе коды бронирования и действительные даты заезда и выезда). Единственная информация, которая потерялась - это время бронирования, так что Пьер не знает приоритетов бронирования (первой заказана – первой обслужена). Используя имеющуюся информацию, не могли бы вы помочь Пьеру и сообщить ему распределение номеров используя минимальное количество комнат так, чтобы удовлетворить все заказы? Обратите внимание на то, что номер должен всегда быть убран перед повторным использованием. Так как Пьер не хочет рисковать, он просит Вас рассматривать только максимальное время уборки.

Вход. Первая строка содержит количество t (1 ≤ t ≤ 100) тестов. Первая строка каждого теста содержит два целых числа: количество бронирований b (1 ≤ b ≤ 5000) и время уборки c (0 ≤ c ≤ 360) (в минутах) для одной комнаты. Каждая из следующих b строк содержит код резервации (произвольная строка из букв и цифр до 20 символов) и даты прибытия и выезда для одного бронирования. Даты заданы в формате "YYYY-MM-DD HH:MM" (как указано в примере), годы резервирования варьируются от 2013 до 2016.

Выход. Для каждого теста выведите в отдельной строке минимальное количество необходимых номеров. Помните о високосных годах, но игнорируйтре Летнее время.

Пример входа	Пример выхода
4 2 120 1 2013-07-01 15:59 2013-07-08 16:30 2 2013-07-08 17:30 2013-07-15 12:00 3 60 65 2013-07-08 14:30 2013-07-08 16:00 32 2013-07-01 16:00 2013-07-15 12:00 91 2013-07-01 16:00 2013-07-08 15:00 2 360 a7 2016-02-21 14:00 2016-02-28 21:00 xx 2016-03-01 01:00 2016-03-02 12:57 2 60 a9 2016-02-21 14:00 2016-02-28 11:00 a8 2016-02-28 12:00 2016-03-11 21:00	2 3 1 1

РЕШЕНИЕ

заметающая прямая

Анализ алгоритма

Бронирование представляет собой отрезок на оси времени. Добавим в конец каждого отрезка еще время c на уборку. Преобразуем время начала и конца бронирования в минуты. Минимальное количество необходимых номеров равно максимальному количеству отрезков, которые одновременно пересекаются.

Занесем точки – концы отрезков в массив, запомнив при этом каким концом (левым или правым) они являются. Далее отсортируем точки по абсциссе. Среди точек с одинаковыми абсциссами сначала расположим те, что соответсвуют концам отрезков. Будем двигаться по оси абсцисс слева направо по точкам (организуем движение заметающей прямой). Вычисляем глубину вложенности depth (пересечения) отрезков.

Реализация алгоритма

Массив mdays хранит количество дней в месяцах.

char s[100];

int mdays[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

Точка содержит абсциссу времени и информацию о том, является ли оно началом или концом интервала.

class Point

{

public:

int x;

char c; // 'b', 'e'

Point(void)

{

x = 0; c = '-';

}

Point(int x, char c) : x(x), c(c) {};

};

Объявим массив точек – он будет содержать концы интервала.

vector<Point> p;

Компаратор для сортировки точек. Если события имеют одно время, то окончание бронирования всегда ставим перед началом.

int f(Point a, Point b)

{

if (a.x == b.x) return a.c > b.c;

return a.x < b.x;

}

Читаем дату начала или конца бронирования, преобразовываем ее в минуты.

int ReadTime(void)

{

int i, days;

int year, mon, day, hour, minute;

scanf("%d-%d-%d %d:%d",&year,&mon,&day,&hour,&minute);

days = (year - 2013) * 365;

for(i = 0; i < mon - 1; i++)

days += mdays[i];

if ((year == 2016) && (mon > 2)) days++;

days = days + day - 1;

return (days * 24 + hour) * 60 + minute;

}

Основная часть программы. Читаем входные данные.

scanf("%d",&tests);

while(tests--)

{

p.clear();

scanf("%d %d",&b,&c);

for(i = 0; i < b; i++)

{

scanf("%s",s);

Читаем время начала бронирования.

t = ReadTime();

p.push_back(Point(t,'b'));

Читаем время конца бронирования, прибавляем к нему c минут для уборки.

t = ReadTime();

p.push_back(Point(t + c,'e'));

}

Сортируем концы отрезков.

sort(p.begin(),p.end(),f);

В переменной depth будем поддерживать глубину вложенности отрезков. Если встречается начало отрезка, то увеличим depth на 1. Если конец отрезка – то уменьшим depth на 1. Наибольшее значение depth вычисляем в res. Оно и равно наибольшему числу отрезков, которые перекрываются в некоторый момент времени.

depth = res = 0;

for(i = 0; i < p.size(); i++)

{

if (p[i].c == 'b') depth++;

if (p[i].c == 'e') depth--;

if (depth > res) res = depth;

}

Выводим ответ.

printf("%d\n",res);

}