Задача ЕГЭ о максимальном количестве одновременно пересекающихся отрезков
Помогите, пожалуйста, c решением 26 задачи из ЕГЭ. Мне нужно просто объяснить решение, ибо то, что было на сайте в ответе, я вообще не понимаю.
Вот условие: Во многих компьютерных системах текущее время хранится в формате «UNIX-время» — количестве секунд от начала суток 1 января 1970 года.
В одной компьютерной системе проводили исследование загруженности. Для этого в течение месяца с момента UNIX-времени 1633046400 фиксировали и заносили в базу данных моменты старта и финиша всех процессов, действовавших в этой системе.
Вам необходимо определить, какое наибольшее количество процессов выполнялось в системе одновременно на неделе, начавшейся в момент UNIX-времени 1634515200, и в течение какого суммарного времени (в секундах) выполнялось такое наибольшее количество процессов.
Входные данные:
Первая строка входного файла содержит целое число N — общее количество процессов за весь период наблюдения. Каждая из следующих N строк содержит 2 целых числа: время старта и время завершения одного процесса в виде UNIX-времени. Все данные в строках входного файла отделены одним пробелом.
Если в качестве времени старта указан ноль, это означает, что процесс был активен в момент начала исследования. Если в качестве времени завершения указан ноль, это означает, что процесс не завершился к моменту окончания исследования.
При совпадающем времени считается, что все старты и завершения процессов происходят одновременно, в начале соответствующей секунды. В частности, если время старта одного процесса совпадает с временем завершения другого и других стартов и завершений в этот момент нет, то количество активных процессов в этот момент не изменяется.
В ответе запишите два целых числа: сначала максимальное количество процессов, которые выполнялись одновременно на неделе, начиная с момента UNIX-времени 1634515200, затем суммарное количество секунд, в течение которых на этой неделе выполнялось такое максимальное количество процессов.
Я пытался решить, но код, который я написал, слишком долго выполняется, если он вообще может выполниться. Код:
start_time = 1633046400 # время начала эксперимента
end_time = 1633046400 + 60*60*24*7 # время конца эксперимента
f = open('26 (2).txt')
n = int(f.readline()) # считываю число процессов
count_start = 0 # счетчик процессов, которые происходят на всем времени эксперимента
current_count = 0 # счетчик процессов, которые происходят лишь на части времени
max_count = 0 # максимальный счетчик процессов, происходящих лишь на части времени
timer_count = 0 # счетчик времени, в течение которого происходило максимальное кол-во процессов
lsp = [] # список с началами процессов
lep = [] # список с концами процессов
for i in range(n):
start_proc, end_proc = f.readline().split() # считываю начало и конец одного процесса
if int(start_proc) <= start_time and (int(end_proc) >= end_time or int(end_proc) == 0): # проверяю, чтобы он происходил на протяжении всего эксперимента
count_start += 1
if (int(start_proc) > start_time and int(end_proc) < end_time) or (int(end_proc) > end_time > int(start_proc) > start_time) or (int(start_proc) < start_time < int(end_proc) < end_time): # проверяю, чтобы он происходил лишь на части эксперимента
lsp.append(start_proc) # добавляю время начала процесса
lep.append(end_proc) # добавляю время конца процесса
lsp = [int(i) for i in sorted(lsp)] # сортирую оба списка
lep = [int(i) for i in sorted(lep)]
for i in range(lsp[0],lep[-1]): # пробегаю через время работы всех процессов
if i in lsp: # прибавляю к счетчику процессов, если встретилось начало какого-либо процесса
current_count += 1
if i in lep: # вычитаю из счетчика процессов, если встретился конец какого-либо процесса
current_count -= 1
if current_count > max_count and start_time < i < end_time: # меняю максимальный счетчик, если нахожусь во времени проведения эксперимента
max_count = current_count
timer_count = 0 # обнуляю счетчик времени
timer_count += 1 # прибавляю ко времени, если счетчик процессов не становится больше
print(count_start + max_count, timer_count) # вывожу счетчики и время
У меня была главная идея в том, что если про проходке по времени работы процессов я встречаю начало какого-либо из них, то прибавляю к счетчику, а если конец, то вычитаю, но из-за больших чисел в файле код не работает.
Ответы (1 шт):
Заметание по времени. Событие хранит изменение количества процессов: + для старта процесса, - для завершения. Все события до начала времён собираются в один счётчик pre_count. Все события после конца времён выбрасываются. События в течении недели упорядочиваются по времени. А ещё завершения располагаются до стартов – это важно для расчёта максимума. max_count_time накапливает время максимальной нагрузки суммируя времена с различными знаками.
Данных нет, не тестировал.
start_time = 1634515200 # время начала эксперимента
end_time = start_time + 60 * 60 * 24 * 7 # время конца эксперимента
with open('26 (2).txt') as f:
n = int(f.readline()) # считываю число процессов
pre_count = 0 # число процессов работающих в момент start_time
events = []
for _ in range(n):
start, end = map(int, f.readline().split()) # считываю начало и конец одного процесса
if start <= start_time:
pre_count += 1
elif start < end_time:
events.append((start, 1))
if 0 < end <= start_time:
pre_count -= 1
elif 0 < end < end_time:
events.append((end, -1))
events.append((start_time, pre_count)) # как-бы стартуем пачку процессов
events.append((end_time, -1)) # ставим в конец что-нибудь
events.sort()
max_count = 0
max_count_time = 0
count = 0
for t, c in events:
if c >= 0:
count += c
if count > max_count:
max_count = count
max_count_time = 0
if count == max_count:
max_count_time -= t
else:
if count == max_count:
max_count_time += t
count += c
print(max_count, max_count_time) # вывожу счетчики и время