Задача #2170

Сортировка

Уровень ЕГЭ

(П. Говоров) Лаборант Яр де Осл для каждого научного экперимента в журнал записывает время начала и время его завершения (в секундах от момента начала исследований). Необходимо определить наибольшее количество экпериментов, которые проводились в лаборатории одновременно, и максимальный отрезок времени, в течение которого проводилось наибольшее количество экпериментов одновременно.

Входные данные представлены в файле следующим образом. Первая строка входного файла содержит количество экпериментов N (N ≤ 10000). Каждая из следующих N строк содержит два целых числа: время начала (T1) и время завершения одного экперимента (T2) (в секундах 0 < T1 ≤ T2 < 5 000 000 ).

Запишите в ответе два числа: наибольшее количество экпериментов, которые проводились в лаборатории одновременно и, максимальный отрезок времени, в течение которого проводилось наибольшее количество экпериментов

Пример входного файла:

4
3 7
6 8
1 9
5 6

В данном случае наибольшее число экпериментов (3) выполнялось в интервале времени между 5 и 7. Ответ: 3 2.

Файлы к задаче

Скачать 26.txt
Ответ
Войдите, чтобы история ответов и статистика сохранялись.
Решение Нажми, чтобы открыть

Ответ

4050
742
В задаче используется метод преф. сумм и алгоритм макс. длины подряд идущих
f = open('26.txt')
n = int(f.readline())
arr_time = [0] * (5*10**6)
for i in range(n):
st, end = map(int, f.readline().split())
arr_time[st] += 1
arr_time[end] -= 1
pref_arr = [0] * len(arr_time)
pref_arr[0] = arr_time[0]
for i in range(1,len(arr_time)):
pref_arr[i] = pref_arr[i-1] + arr_time[i]
mx_odn = max(pref_arr)
k = 0
mx_k = 0
for i in pref_arr:
if i == mx_odn:
k += 1
mx_k = max(k, mx_k)
else:
k = 0
print(mx_odn, mx_k)
Быстрый переход
Перейти к задаче