python - 寻找最繁忙时段的算法？

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

        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))

也可以将这个想法转化为online algorithm如果您在程序开始时没有完整的间隔列表，但可以保证传入的间隔永远不会被安排在过去的时间点。代替排序，您将使用优先级队列，每次间隔到来时，您都会插入两个项目，起点和终点，每个项目分别带有 +1 和 -1。然后你弹出并计算并跟踪高峰时段。