寻找最繁忙时期的算法？

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和min为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))

如果您在程序开始时没有完整的间隔列表,但可以保证传入的间隔永远不会安排在过去的点上,也可以将此想法转换为在线算法.不是排序,你将使用优先级队列,每当一个间隔到来时,你推入两个项目,起点和终点,每个项目分别为+1和-1.然后你弹出并计算并跟踪高峰时段.

Answer 2

我首先想到点x的忙碌作为x左边的激活次数减去x左边的去激活次数.我会根据它们发生的时间(在O(nlog(n))时间内对激活和停用进行排序).然后,您可以遍历列表,跟踪活动数字(y),递增和递减该数字,同时激活和停用.最繁忙的时期将是y处于最大值的点.我无法想到一个比O(nlog(n))更好的解决方案.蛮力将是O(n ^ 2).