Информационная система выполняет сложные запросы. Для анализа нагрузки системы и её колебаний в течение суток в протокол занесли все запросы, выполненные в течение одного календарного дня. Для каждого запроса указаны время начала и время конца обработки.
Входные данные.
Первая строка входного файла содержит целое число N (N ≤ 1 000 000) — общее количество запросов. Каждая из следующих
Например, если t1 = 10 и t 2 = 15, то обработка запроса началась через
Определите наибольшее количество запросов, которые одновременно находились в обработке в период с 8:00 до 14:00, и общую продолжительность времени (в секундах) в этот период, в течение которого выполнялось такое максимальное количество запросов. Запросы, выполнение которых попало в указанный интервал частично, тоже следует учитывать.
В ответе запишите два целых числа: сначала максимальное количество одновременно выполняемых запросов, затем общую продолжительность времени, в течение которого выполнялось такое количество запросов.
Ответ:
Приведем решение на языке Python.
f = open('26.txt')
n = f.readline()
sytki = [0]*86400
start = 8*60*60
end = 14*60*60
zapros = 0
for s in f:
t1,t2 = map(int,s.split())
for i in range(t1,t2):
sytki[i] += 1
zapros = max(sytki[start:end+1])
time_zapros = sytki.count(zapros)
print(zapros, time_zapros)
Ответ: 4984&1.
Приведем решение Бориса Савельева на языке Python.
f=open('26.txt')
n=int(f.readline())
a=[0]*24*60*60
t1=8*60*60
t2=14*60*60
for i in range (0,n):
x,y = map(int,f.readline().split())
if x<=t1 and y>=t2:
for j in range (t1,t2):
a[j]+=1
elif x<=t1 and y<=t2:
for j in range (t1,y):
a[j]+=1
elif x>=t1 and y>=t2:
for j in range (x,t2):
a[j]+=1
elif x>=t1 and y<=t2:
for j in range (x,y):
a[j]+=1
print(max(a),a.count(max(a)))
Приведем решение Юрия Красильникова на языке Python.
_, *a = [list(map(int,s.split())) for s in open('26.txt')]
dic = {}
for t1,t2 in a:
dic[t1]=dic.get(t1,0)+1
dic[t2]=dic.get(t2,0)-1
tt = sorted([[t,dic[t]] for t in dic if dic[t] != 0])
for i in range(1,len(tt)): tt[i][1] += tt[i-1][1]
tt0 = [t for t in tt if 8*3600 <= t[0] <= 14*3600]
mp = max([x[1] for x in tt0])
d = sum([(tt0[i][0]-tt0[i-1][0]) for i in range(1,len(tt0)) if tt0[i-1][1] == mp])
print(mp,d)