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

Question

我有上百个元组的列表如下：

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

每个元组都以一个历元的形式包含会话的开始和结束。你知道吗

我想找到的是同时发生的最大会话数。所以如果epoch1 = 16:00, epoch2=16:30, epoch3=16:15, epoch4=16:45, epoch5=18:00, epoch6=19:00，答案是2，因为从16:15 to 16:30开始有两个会话处于活动状态（第一个会话和第二个会话）。你知道吗

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

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

然后遍历list2中的每一对元素，并检查会话边界中有多少list1元组包含这些元素。但我想这个解决方法很慢。有人有其他想法吗？你知道吗

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)

Answer 2

好吧，让我们想想你所问的最简单的问题。
同时运行多少个会话？
作为一个人类，你会如何看待这个问题？你知道吗

好吧，对于同时出现的时代来说：

• 一个时代的开始需要到来 在另一个时代的开始和结束之前。你知道吗
• 或者一个时代的结束需要介于开始和结束之间 在另一个时代结束之前。你知道吗

但当你想到这些都是一样的事情，因为一个是真的，另一个必须是真的。

这意味着您可以检查每个元组中的第一个元素是否位于任何其他元组的两个元素之间：

 count = 0
 for tuple1 in list1:
     for tuple2 in list1:
          if tuple2[1] > tuple1[0] > tuple2[0]:
              count += 2 #this means two overlap

Answer 3

这是一个经典问题。假设酒店需要为会议安排房间，这些会议的开始和结束时间是给定的。需要多少房间？让我试着记住解决办法。你知道吗

首先，把会议按开始时间排序。现在假设有无限数量的房间。第一次会议安排在一号房间。对于第二次会议，如果第一会议室的会议在第二次会议开始时结束，则安排在第一会议室，否则安排在第二会议室。对于每次连续的会议，查看所有的会议室。如果有人空缺，就在那里安排会议。如果没有，请添加一个新房间。你知道吗

为了确保这一点，请注意，我们需要的最小房间数是同时举行会议的最大数量，因为每个会议都在不同的房间中进行。该算法提供了一种在这么多房间中安排会议的方法，因为我们从不添加新房间，除非会议开始时所有现有房间都已被占用。len(ending)是同时开会次数的高水位线。你知道吗

在python中，我们只需要一个结束时间列表。设置ending[0] = epoch2。对于每次会议，循环查看结束列表。如果发现时间早于新会议的开始时间，请将其更改为新会议的结束时间。如果不是，则在结尾处添加新元素。最后，len(ending)就是答案。你知道吗

每次更改结束列表时，对其进行排序可能是值得的，因为这样可以清楚地检查最早的结束时间。你知道吗

进一步的信息：这个问题可以建模为一个图，其中区间是顶点，两个顶点是相邻的当且仅当它们相交时。现在我们可以用表示房间的颜色来给顶点上色，相邻的两个顶点不能有相同的颜色。所需的最小颜色数就是答案。奇怪的是，这种类型的图称为区间图。区间图有许多应用。https://en.wikipedia.org/wiki/Interval_graph求图的色数一般是NP困难的，但该算法表明区间图的色数可以在多项式时间内计算。你知道吗