Система наблюдения ежеминутно фиксирует вход и выход сотрудников из офиса (в минутах, прошедших от начала суток). Считается, что в моменты фиксации входа и выхода сотрудник находится в офисе. Нулевая минута соответствует моменту начала рабочего дня в офисе, который длится 24 ч в сутки без перерыва.
Менеджер компании анализирует данные системы наблюдения за прошедшие сутки, и выявляет непересекающиеся отрезки времени наибольшей длины, в течение которых число сотрудников, находящихся в офисе, не изменялось.
Входной файл содержит время входа и выхода каждого сотрудника компании. Определите минуту, когда в предпоследний раз за сутки число сотрудников поменялось, и укажите наибольшую длину отрезка времени, когда количество сотрудников оставалось неизменным.
Входные данные
В первой строке входного файла находится натуральное число N (N ≤ 100 000) — количество сотрудников компании.
Следующие N строк содержат пары чисел, обозначающих соответственно время входа и время выхода сотрудника (все числа натуральные, не превышающие 1440).
Запишите в ответе два натуральных числа: сначала минуту, когда в предпоследний раз за сутки число сотрудников поменялось, а затем наибольшую длительность промежутка времени, при котором количество сотрудников оставалось неизменным.
Типовой пример организации данных во входном файле
5
10 1070
230 1070
240 1070
1070 1400
1071 1400
При таких исходных данных в течение суток было 7 промежутков времени, когда число сотрудников не менялось: (0, 10), (10, 230), (230, 240), (240, 070), (1070, 1071), (1071, 1400), (1400, 1440). Наибольшей длиной из этих отрезков является число 830. В 1071 минуту в предпоследний раз за сутки изменилось число сотрудников.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Ответ:
Приведём решение Юрия Красильникова на языке Python.
f=open('26.txt')
f.readline()
times=[0]*1440
for s in f:
t1,t2=map(int, s.split())
for t in range(t1,t2+1): times[t]+=1
dlit=[1]
smena=[]
for i in range(1,len(times)):
if times[i-1]==times[i]: dlit[-1]+=1
else:
dlit.append(1)
smena.append(i)
print(smena[-2],max(dlit))
Ответ: 1432; 15.
Приведём решение Юрия Красильникова на языке Python.
f=open('26.txt')
f.readline()
dic={}
for s in f:
t1,t2=map(int, s.split())
dic[t1]=dic.get(t1,0)+1
dic[t2+1]=dic.get(t2+1,0)-1
tt=sorted([t for t in dic if dic[t]!=0])
if tt[0]!=0: tt=[0]+tt
if tt[-1]!=1440: tt=tt+[1440]
print(tt[-3],max([tt[i]-tt[i-1] for i in range(1,len(tt))]))