Самый эффективный способ найти точку, где максимальное количество интервалов перекрывается с питоном

Question

Предположим, у меня есть журнал регистрации времени входа и выхода пользователей с какого-либо сервера.Мне нужно найти время, в которое проводятся максимальные сессии.Если существует более одного возможного ответа, должен быть выбран самый маленький.Вход содержит количество сессий в первой строке.

Пример ввода:

5
4 5
0 3
1 9
7 8
2 6

Выход:

2

Я пробовал этот скрипт:

from collections import Counter, OrderedDict

load = Counter()
with open("input.txt", "r") as f:
    n = int(f.readline())
    for i in range(n):
        session = f.readline()
        session = session.split()
        load.update(range(int(session[0]), int(session[1])+1))

load = load.most_common()
i = 0
max = load[0][1]
candidates = []
while load[i][1] == max:
    candidates.append(load[i][0])
    i += 1
print(min(candidates))

Сначала я использую Counter() для подсчета вхождений всех точек.Во-вторых, я использую load = load.most_common(), чтобы упорядочить результирующий дикт по происшествиям.Наконец, я нахожу минимальное значение всех ключей с соответствующим максимальным значением (= количество вхождений).

На самом деле, если бы Counter() вернул диктовку, упорядоченную по ключу, это было бы намного проще.

В любом случае, это моя домашняя задача, и она выполняется более 1 секунды (с учетом ограничения по времени) на одном из тестовых входов.Что можно сделать, чтобы ускорить его?Я читал о деревьях интервалов, но я не уверен, что это уместно.

Answer 1

Допустим, ins и outs - время входа и выхода:

ins = [4,0,1,7,2]
outs = [5,3,9,8,6]

Объедините их в один отсортированный список со знаком числа, указывающего, является ли это "прибытием"(положительный) или «отъезд» (отрицательный):

times = sorted(ins + [-x for x in outs], key=abs)

Теперь пройдитесь по списку и посчитайте «прибытия» и «отправления» по мере их появления:

lmax = -1
logged = 0
for t in times:
    if t >= 0:
        logged += 1
        if logged > lmax:
            tmax = t
            lmax = logged
    else:
        logged -= 1

print(tmax, lmax)
#2 3

Answer 2

Быстрое решение для этого - просто сохранить +1, -1 во время входа / выхода - затем отсортировать клавиши dict и постепенно суммировать их с последующим получением максимального значения:

data = """5
4 5
0 3
1 9
7 8
2 6"""
with open("input.txt", "w") as f:
    f.write(data) 

d = {}
with open("input.txt", "r") as f:
    next(f)
    for line in f:  
        if line.strip():
            start, stop = map(int,line.strip().split())
            d.setdefault(start,0)
            d[start] += 1
            d.setdefault(stop,0)
            d[stop] -= 1

maxx = 0
s = 0
max_idx = 0

# iteratively summ over sorted times from dict
for idx,key in enumerate(sorted(d)):
    s += d[key]
    if maxx < s:  # remembert new max_idx and max
        maxx = s
        max_idx = idx
print(max_idx)

Вы можете использовать defaultdict (int), если он все еще слишком медленный, чтобы решить вашу проблему.