寻找最繁忙时段的算法？
我有一些这样的数据：
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。这不是整个算法，但应该给出我在这里所做的一个高级概念。我会看看我是否能画出伪代码。
回答 6
Stack Overflow用户
发布于 2011-04-24 13:04:25
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。然后你突然停下来，数一数，记录下高峰时间。
Stack Overflow用户
发布于 2011-04-24 12:49:27
我会从x左边的激活次数减去x左边的停用次数开始考虑点x的繁忙程度。我会按照激活和停用发生的时间(在O(nlog(n))时间内)对激活和停用进行排序。然后，您可以遍历列表，跟踪活动数量(y)，通过传递激活和停用来递增和递减该数字。最繁忙的时期将是y达到最大值的点。我脑海中想不出比O(nlog(n))更好的解决方案。蛮力将是O(n^2)。
Stack Overflow用户
发布于 2011-04-24 12:55:53
我想您可能会为此使用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提到的那样创建bin对。
https://stackoverflow.com/questions/5768642
复制相似问题
腾讯云开发者
