Задача 12.
В музее регистрируется в течение дня время прихода и ухода каждого посетителя. Таким образом за день получены N пар значений, где первое значение в паре показывает время прихода посетителя и второе значения - время его ухода. Найти промежуток времени, в течение которого в музее одновременно находилось максимальное число посетителей.
|
Решение задачи 12.
Будем представлять посещение музея посетителем в виде отрезка [время_прихода_посетителя, время_ухода_посетителя]. Надо найти множество точек, принадлежащих максимальному числу отрезков (они и будут составлять тот промежуток (промежутки) времени, в течение которого в музее одновременно находилось максимальное число посетителей.
Рассмотрим какой-нибудь такой промежуток. Его концами, очевидно, являются концевые точки каких-то двух отрезков. В решении задачи 8 (Дихотомия и поиск) в переменной С храниться количество отрезков, пересекающихся в текущей концевой точке. Сначала мы найдем Cmax - максимальную величину переменной C, затем определим, каким промежуткам соответствует максимальное количество посетителей в музее:
{смысл массива A см. в задаче 8 (Дихотомия и поиск)}
{находим Cmax}
i:=1; Cmax:=0;
пока (i<=2*N) и
повторять
если A[2,i]>0
то C:=C+1;
Cmax:=max(Cmax, C);
конец_то
иначе C:=C-1;
конец_иначе
i:=i+1;
конец_пока
если Сmax=0,
то посетителей не было вообще. Стоп.
{ищем и печатаем промежутки с максимальным числом посетителей}
i:=1;
пока (i<=2*N) и
повторять
если A[2,i]>0
то C:=C+1;
если С=Смах {это начало искомого промежутка?} то печатаем координату начала промежутка A[1,i] конец_то
конец_то
иначе
если С=Смах {промежуток закончился}
то печатаем координату конца промежутка A[1,i]
конец_то
C:=C-1;
конец_иначе
i:=i+1;
конец_пока
|
