找到最大间隔与python重叠的点的最有效方法 [英] The most efficient way to find the point where maximum number of intervals overlap with python

问题描述

考虑一下，我有一个日志寄存器，用于记录用户从某些服务器进入和退出的时间.我需要找到最大会话数的时间.如果有多个答案，则应选择最小的答案.输入的内容包含第一行中的会话数.

Consider I have a log register for users' entry and exit times from some server. I need to find the time at which there are maximum sessions. If there are more than one possible answer, the smallest should be chosen. The input contains the number of sessions in the first line.

示例输入:

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()对出现的字典进行排序.最后，我找到所有键的最小值和相应的最大值(=出现的次数).

First, I use Counter() to count the occurrences of all points. Second, I use load = load.most_common() to order the resulting dict by occurrences. Finally I find the minimum value of all keys with the corresponding maximum value (= # of occurrences).

实际上，如果 Counter()返回一个按键排序的字典，则它将简单得多.

In fact, if Counter() returned a dict ordered by key, it would be much simpler.

无论如何，这是我的主任务，并且在其中一个测试输入上运行超过1秒(给定的时间限制).可以采取什么措施来加快速度?我已经读过有关间隔树的信息，但是不确定是否相关.

Anyway, it is my home task and it runs more than 1 second (given time limit) on one of the test inputs. What could be done to speed it up? I've read about interval trees but I'm not sure if it is relevant.

推荐答案

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

Let's say ins and outs are the log in and log out times:

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

在一个已排序的列表中将其组合在一起，并用数字的符号表示它是到达"(正)还是出发"(负):

Combine them in one sorted list with the sign of the number indicating whether it is an "arrival" (positive) or "departure" (negative):

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

现在，遍历列表并计算发生的到达"和离开":

Now, walk through the list and count the "arrivals" and "departures" as they happen:

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重叠的点的最有效方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！