在元组列表中获得最大并发的有效方法是什么？

我一直在努力以有效的方式解决这个问题。问题是：

问题陈述

给定以下形式的元组列表[(start1, end1), (start2, end2), (start3, end3)....(startn, endn)]其中 start 和 end 是正整数。每个元组代表一个时间窗口，例如：[(1, 3), (73, 80)...]。查找发生最大并发的时间（整数）并获取发生最大并发的元组。

限制条件：

1. start and end是时间的整数，介于 0 到 n 之间
2. 对于所有情况start < end
3. start是包容性的，但是end是排他性的
4. 对于最大并发发生的时间（整数），如果有多种情况，我们只能得到一个

例如，下面的时间表将在时间 2 处具有 max_concurrency，并且元组为 (0,3)、(2,3)、(1, 200) 具有该值。

schedule = [
            (0, 3),
            (3, 5),
            (2, 3),
            (6, 8),
            (10, 12),
            (73, 92),
            (1, 200),
            ]

My Code

发生最大并发的时间。如果我错了请纠正我，但我认为这是正确的O(n^2) time.

from collections import defaultdict

schedule_dict = defaultdict(lambda: 0)

for start, end in schedule:
    for time in range(start, end):
            schedule_dict[time] += 1

max_concurrency = max(schedule_dict, key=schedule_dict.get)
print(f"Time where max concurrency happens is : {max_concurrency}")

Output

Time where max concurrency happens is : 2  

对于发生最大并发的会话，我认为这运行在O(n) time.

My Code

for start, end in schedule:
    if start <= max_concurrency < end:
        print(f"{(start, end)}")

Output

(0, 3)
(2, 3)
(1, 200)

最后我的问题

有什么更有效的方法可以降低时间和空间复杂度？

与任何时刻 T 重叠的间隔数量是小于或等于 T 的间隔开始时间的数量减去小于或等于 T 的间隔结束时间的数量。

1. 将开始时间和结束时间放在单独的列表中，并对它们进行排序。
2. 将深度计数器初始化为 0
3. 按顺序遍历列表（如合并排序），每个开始时间加 1，每个结束时间减 1
4. 请记住，当计数器达到最大值时——那就是最大重叠的时间。

这是 python 中的实现：

schedule = [
  (0, 3),  (3, 5), (2, 3), (6, 8),
  (10, 12), (73, 92), (1, 200),
  ]

starts = [x[0] for x in schedule]
ends = [x[1] for x in schedule]

starts.sort()
ends.sort()

endpos = 0
depth = 0
maxdepth = 0
maxdepthtime = -1

for time in starts:
    depth+=1
    while endpos < len(ends) and ends[endpos]<= time:
        depth -= 1
        endpos += 1
    if depth > maxdepth:
        maxdepth = depth
        maxdepthtime = time

overlappers = [x for x in schedule
    if (x[0] <= maxdepthtime and x[1] > maxdepthtime)]

print ("Max overlap at time: ", maxdepthtime, " depth ", maxdepth)
print ("Intervals: ", overlappers)