找到最大间隔数与 python 重叠的点的最有效方法

Question

假设我有一个记录用户从某个服务器进入和退出时间的日志记录。我需要找到最大会话的时间。如果有多个可能的答案，应选择最小的答案。输入包含第一行的会话数。

例子输入：

输出：

我试过这个脚本：

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()返回一个key排序的dict，就简单多了。

无论如何，这是我的家庭任务，它在其中一个测试输入上运行超过 1 秒（给定时间限制）。可以做些什么来加快速度？我读过有关间隔树的信息，但不确定它是否相关。

Answer 1

这个问题的快速解决方案是将 +1、-1 存储在 enter/exit 次 - 然后对 dict-keys 进行排序并递增求和，然后获得最大值：

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) 仍然太慢而无法解决您的挑战，您可以使用 defaultdict(int)。

Answer 2

假设 ins 和 outs 是登录和注销时间：

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

将它们组合在一个排序列表中，并用数字符号表示它是 "arrival"（正数）还是 "departure"（负数）：

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

现在，遍历列表并计算 "arrivals" 和 "departures" 的发生次数：

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

找到最大间隔数与 python 重叠的点的最有效方法

The most efficient way to find the point where maximum number of intervals overlap with python

python

algorithm

intervals