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

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

这是一个经典问题。假设酒店需要为指定开始和结束时间的会议安排房间。需要多少房间？让我试着记住解决方案。

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

要查看这是否有效，请注意我们需要的最小房间数是同时举行会议的最大数量，因为每个会议都发生在不同的房间。该算法提供了一种在这么多房间内安排会议的方法，因为除非在会议开始时所有现有房间都被占用，否则我们永远不会添加新房间。 len(ending) 是同时会议数的 high-water 标记。

要在 python 中执行此操作，我们只需要一个结束时间列表。设置 ending[0] = epoch2。对于每次会议，循环遍历结束列表。如果发现早于新会议的开始时间，将其更改为新会议的结束时间。如果不是，则将新元素附加到结尾。最后，len(ending)就是答案。

可能值得在每次更改结束列表时对其进行排序，因为它足以清楚地检查最早的结束时间。

更多信息：问题可以建模为图形，其中间隔是顶点，两个顶点相邻当且仅当它们相交时。现在我们可以用代表房间的颜色给顶点上色，并且任何两个相邻的顶点都不能有相同的颜色。所需的最少颜色数就是答案。奇怪的是，这种类型的图称为区间图。区间图有很多应用。 https://en.wikipedia.org/wiki/Interval_graph求一个图的色数一般是NP-hard，但是这个算法表明区间图的色数可以在多项式时间内求出

Answer 2

好吧，让我们考虑一下您所问内容的最简单细分。
同时运行有多少会话？
作为人类，您如何看待这个？

好吧，对于要同时出现的纪元：

One epoch would the epoch would need to be come 在另一个纪元的开始和结束之前。
或者一个纪元的结束需要介于开始之间另一个时代和它结束之前。

但是当你想到这些是同一件事时，因为要使一个为真，另一个必须为真。

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

 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

两种 O(n log n) 方式

设置：

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

第一种方式：将starts和ends变成事件（epoch+change pairs），按升序遍历，适当更新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)

第二种方式：独立排序开始和结束，然后遍历它们"in parallel"，更新需要的槽数和当前空闲的槽数。

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)

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

How to find the biggest common range?

python

algorithm

datetime

intervals