寻找最繁忙时间段的算法？

Question

我有一些数据，像这样：

1: 2 - 10
2: 3 - 15
3: 4 - 9
4: 8 - 14
5: 7 - 13
6: 5 - 10
7: 11 - 15

我会尝试用一种方式来表示，让它更清晰：

        1     2     3     4     5     6     7     8     9     10     11     12     13     14     15
1             |--------------------------------------X---------|
2                   |--------------------------------X--------------------------------------------|
3                         |--------------------------X---|
4                                                  |-X-------------------------------------|
5                                           |--------X------------------------------|
6                               |--------------------X----------|
7                                                                     |---------------------------|

在这个例子中，如果使用第二种方案，8-9就是关键的时间段，因为所有的点都是活跃的。有没有快速又好的方法在Python中解决这个问题？我在考虑使用动态规划，但有没有其他推荐的方法呢？

到目前为止我的想法：

我更倾向于从实时的角度考虑。所以，每当我收到一个新点时，我会这样做：假设我已经得到了2-10，然后我又得到了3-15，那么我会选择开始时间的最大值和结束时间的最小值，这样就变成了3-10，并把这个区间的计数加到2。接着第三个点4-9来了，我选择最大值是4，最小值是9，然后把3-10更新为4-9，计数更新为3。现在当8-14到来时，我发现这个区间的开始时间大于4-9的开始时间，而结束时间小于4-9的结束时间。这种情况下不成立，所以我会创建一个新的区间8-14，并把计数设为1。这不是整个算法，但应该能给你一个大致的想法我在做什么。我会看看能否画出伪代码。

Answer 1

我觉得你可以用一个集合（set()）来解决这个问题，如果你能确保所有的时间段至少有一个交点的话，这样是可以的。

不过，一旦有一个时间段没有交点，这个方法就不管用了。你可能需要添加一些额外的逻辑来处理这种情况，所以我想分享一下我的想法：

>>> periods = [(2, 10), (3, 15), (4, 9), (8, 14), (7, 13), (5, 10),]
>>> intersected = None
>>> for first, second in periods:
...     if not intersected:
...         intersected = set(range(first, second + 1))
...     else:
...         intersected = intersected.intersection(set(range(first, second + 1)))
...
>>> intersected
set([8, 9])

注意：这段代码没有包括11到15这个时间段。你最好还是按照R.K.提到的方法来创建时间段的配对。

Answer 2

我会先考虑一个点 x 的“忙碌程度”，这可以通过计算 x 左边的激活次数减去左边的停用次数来得到。接下来，我会把所有的激活和停用事件按照发生的时间排序，这个过程的时间复杂度是 O(nlog(n))。然后，你可以遍历这个列表，记录当前活跃的数量（记作 y），每遇到一个激活事件就加一，遇到一个停用事件就减一。最忙碌的时间段就是 y 达到最大值的那些点。我想不出比 O(nlog(n)) 更好的解决方案，最简单粗暴的方法时间复杂度是 O(n^2)。

Answer 3

        1     2     3     4     5     6     7     8     9     10     11     12     13     14     15
1             |--------------------------------------X---------|
2                   |--------------------------------X--------------------------------------------|
3                         |--------------------------X---|
4                                                  |-X-------------------------------------|
5                                           |--------X------------------------------|
6                               |--------------------X----------|
7                                                                     |---------------------------|

             +1    +1     +1   +1           +1     +1    -1    -2     +1           -1     -1     -2
              1     2     3     4           5       6    5      3     4             3      2      0
                                                     ^^^^

明白了吗？

所以你需要把这个：

1: 2 - 10
2: 3 - 15
3: 4 - 9
4: 8 - 14
5: 7 - 13
6: 5 - 10
7: 11 - 15

转变成：

[(2,+), (3,+), (4,+), (5,+), (7,+), (8,+), (9,-), (10,-), (10,-), (11,+), (13,-), (14,-), (15,-), (15,-)]

然后你只需要遍历这个数据，每当看到一个加号（+）就加一，看到一个减号（-）就减一。最繁忙的时间段就是当这个计数达到最大值的时候。

在代码中：

intervals = [(2, 10), (3, 15), (4, 9), (8, 14), (7, 13), (5, 10), (11, 15)]
intqueue = sorted([(x[0], +1) for x in intervals] + [(x[1], -1) for x in intervals])
rsum = [(0,0)]
for x in intqueue: 
    rsum.append((x[0], rsum[-1][1] + x[1]))
busiest_start = max(rsum, key=lambda x: x[1])
# busiest_end = the next element in rsum after busiest_start 

# instead of using lambda, alternatively you can do:
#     def second_element(x):
#         return x[1]
#     busiest_start = max(rsum, key=second_element)
# or:
#     import operator
#     busiest_start = max(rsum, key=operator.itemgetter(1))

运行复杂度是 (n+n)*log(n+n)+n+n 或者 O(n*log(n))

如果你在程序开始时没有完整的时间段列表，但可以保证新来的时间段不会安排在过去的时间点，你也可以把这个想法转化为一种 在线算法。这样你就不需要排序，而是使用一个优先队列。每当有一个时间段到来时，你就把开始点和结束点各推入队列，分别标记为+1和-1。然后你就可以弹出这些数据，进行计数，并记录下最繁忙的时间。