26.04 Прочие прототипы
Ошибка.
Попробуйте повторить позже
Во многих компьютерных системах текущее время хранится в формате «UNIX-время» –— количестве секунд от начала
суток 
января 
года.
В одной компьютерной системе проводили исследование загруженности. Для этого в течение месяца с момента
UNIX-времени 
фиксировали и заносили в базу данных моменты старта и финиша всех процессов,
действовавших в этой системе.
Вам необходимо определить, какое наибольшее количество процессов выполнялось в системе одновременно на неделе,
начавшейся в момент UNIX-времени 
, и в течение какого суммарного времени (в секундах) выполнялось такое
наибольшее количество процессов.
Входные и выходные данные:
Первая строка входного файла 6.txt содержит целое число N –— общее количество процессов за весь период
наблюдения. Каждая из следующих N строк содержит 
целых числа: время старта и время завершения одного процесса в
виде UNIX-времени. Все данные в строках входного файла отделены одним пробелом.
Если в качестве времени старта указан ноль, это означает, что процесс был активен в момент начала исследования. Если в качестве времени завершения указан ноль, это означает, что процесс не завершился к моменту окончания исследования.
При совпадающем времени считается, что все старты и завершения процессов происходят одновременно, в начале соответствующей секунды. В частности, если время старта одного процесса совпадает с временем завершения другого и других стартов и завершений в этот момент нет, то количество активных процессов в этот момент не изменяется.
В ответе запишите два целых числа: сначала максимальное количество процессов, которые выполнялись одновременно
на неделе, начиная с момента UNIX-времени 
, затем суммарное количество секунд, в течение которых на этих
неделях выполнялось такое максимальное количество процессов.
Решение 1
f = open(r"C:\\Users\\Тимофей\Desktop\\n3.txt")
start_week = 1_634_515_200
finish_week = start_week + 7 * 24 * 60 * 60
start_month = 1_633_046_400
finish_month = start_month + 31 * 24 * 60 * 60
n = int(f.readline())
st, fn = [], [] # st - массив стартов, fn - массив финишей
k, maxim = 0, 0 # k - число сейчас активных процессов, maxim - максимальное число активных процессов на неделе
for i in range(n):
a, b = map(int, f.readline().split()) # a, b - время начала и конца i-го процесса
if a == 0: # Если процесс начался до исследования
a = start_month
st.append(a)
if b == 0: # Если процесс кончился после исследования
b = finish_month
fn.append(b)
st.sort()
fn.sort()
# 2 указателя: i - для стартов, j - для финишей
i, j = 0, 0
while i < len(st):
if st[i] < fn[j]:
k += 1
# if для случая, когда ни один процесс не начинается на неделе
if (i < len(st) - 1) and st[i] < start_week and st[i + 1] > finish_week:
maxim = max(maxim, k)
if k > maxim and st[i] >= start_week and st[i] < finish_week:
maxim = k
i += 1
else:
k -= 1
j += 1
i, j = 0, 0
k, ans = 0, 0
for sec in range(start_month, finish_month):
# считаем число начатых и кончившихся процессов в каждую секунду sec
while i < len(st) and st[i] == sec:
k += 1
i += 1
while j < len(fn) and fn[j] == sec:
k -= 1
j += 1
if k == maxim:
ans += 1 # промежуток [sec; sec + 1)
print(maxim, ans)
Решение 2
f = open(r"C:\\Users\\Тимофей\Desktop\\n3.txt")
n = int(f.readline())
start_month = 1_633_046_400
finish_month = start_month + 31 * 24 * 60 * 60
start_week = 1_634_515_200
finish_week = start_week + 7 * 24 * 60 * 60
k = 0
borders = []
for sec in range(n):
x, y = map(int, f.readline().split())
if x == 0:
x = start_month
if y == 0:
y = finish_month
borders.append([x, 1])
borders.append([y, -1])
borders.append([start_week + 1, 0])
borders.sort()
maxim = -1000000000000
time = sorted(set(x[0] for x in borders))
t = 0
ans = 0
for sec in time:
while t < len(borders) and borders[t][0] == sec:
k += borders[t][1]
t += 1
if k > maxim and sec >= start_week and sec < finish_week:
maxim = k
if sec > finish_week:
break
t = 0
k = 0
for sec in range(start_month, finish_month):
while t < len(borders) and borders[t][0] == sec:
k += borders[t][1]
t += 1
if k == maxim:
ans += 1
print(maxim, ans)
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
