python - 查找一组间隔中的重叠间隔

Question

我们有一个登录系统，可以跟踪人们的连接时间。我想编写一个代码来查找同时在线的人。请看这个例子:

P1: [1,7]
P2: [2,5]
P3: [3,4]
P4: [6,8]

将这些视为人物 1 到人物 4 的间隔。我希望算法的输出如下所示:

P1, P2 : [2, 3]
P1, P2, P3 : [3, 4]
P1, P2 : [4, 5]
P1, P4 : [6,7]

我尝试用两个 for 循环来解决这个问题，以便我们得到一个时间间隔重叠的人的列表，但问题是处理多个人的时间间隔。例如，在上面的例子中，[3,4]不必出现在第三行的[4, 5]中，因为它是按三人间隔计算的。

Answer 1

以 1:+P1、7:-P1 等形式对所有区间边界进行编码。然后按时间顺序对所有边界进行排序，并按时间增加进行扫描。还可以通过“执行”插入或删除操作来更新在场人员的列表。

{} 1:+P1 {P1} 2:+P2 {P1, P2} 3:+P3 {P1, P2, P3} 4:-P3 {P1, P2} 5:-P2 {P1} ...

每个配置都发生在一个时间限制和下一个时间限制之间。

某些配置可能会随着时间的推移而重复，但您没有指定如何处理它们。通过上述方法，它们将被单独列出。