python - 如何找到最大的共同范围？

Question

我有一个包含数百个这样的元组的列表:

list1 = [(epoch1, epoch2), (epoch3, epoch4), (epoch5, epoch6)]

每个元组都以纪元的形式包含 session 的开始和结束。

我要查找的是同时发生的最大 session 数。所以如果 epoch1 = 16:00, epoch2=16:30, epoch3=16:15, epoch4=16:45, epoch5=18:00, epoch6=19:00, 答案是 2，因为从 16:15 到 16:30 有两个 session 处于事件状态(第一个和第二个)。

我认为一种方法是创建一个包含所有日期的新列表，如下所示:

list2 = [epoch1, epoch2, epoch3, epoch4, epoch5, epoch6]  

然后遍历 list2 中的每一对元素，并检查有多少 list1 元组在其 session 边界中包含它们。但我想这个解决方案非常慢。有没有人有其他想法？

Answer 1

两种 O(n log n) 方式

设置:

sessions = [('16:00', '16:30'), ('16:15', '16:45'), ('18:00', '19:00')]

第一种方式:将开始和结束变成事件(epoch+change 对)，按升序遍历它们，并适当更新active 和maxactive。

events = (event
          for start, end in sessions
          for event in ((start, 1), (end, -1)))
active = maxactive = 0
for _, change in sorted(events):
    active += change
    maxactive = max(maxactive, active)
print(maxactive)

第二种方式:独立排序开始和结束，然后“并行”遍历它们，更新所需槽的数量和当前空闲槽的数量。

starts, ends = map(sorted, zip(*sessions))
slots = free = e = 0
for start in starts:
    while ends[e] <= start:
        free += 1
        e += 1
    if free:
        free -= 1
    else:
        slots += 1
print(slots)