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

我有一些这样的数据:

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是关键时段，因为所有点均处于 Activity 状态。用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。这不是整个算法，但应该对我在这里所做的事情有一个较高的了解。我将看看是否可以草绘伪代码。

最佳答案

        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。然后您弹出并计算并跟踪高峰时间。

关于python - 寻找最繁忙时段的算法？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/5768642/