在时间范围列表中查找（数量）重叠

以下是一个数据集，显示来自的呼叫间隔为10分钟，我试图找到该间隔中最大活动行数。即。从下面的例子中，什么是活跃的同时呼叫的最大数量：

CallStart CallEnd 
2:22:22 PM 2:22:33 PM 
2:22:35 PM 2:22:42 PM 
2:22:36 PM 2:22:43 PM 
2:22:46 PM 2:22:54 PM 
2:22:49 PM 2:27:21 PM 
2:22:57 PM 2:23:03 PM 
2:23:29 PM 2:23:40 PM 
2:24:08 PM 2:24:14 PM 
2:27:37 PM 2:39:14 PM 
2:27:47 PM 2:27:55 PM 
2:29:04 PM 2:29:26 PM 
2:29:31 PM 2:29:43 PM 
2:29:45 PM 2:30:10 PM

如果有人知道的alogrithm或者可以点我在正确的方向，我将不胜感激。

TIA，

史蒂夫˚F

来源

2010-02-11 Steve F

怎么样天真的做法：

以最少的开始时间和最伟大的时代结束（这是你的范围R）
取最短通话时间-d（排序，O（nlog n））
创建数组C的ceil（R/d）整数，零初始化
现在，对于每个呼叫，添加1〜定义呼叫的持续时间澳细胞（n *小区（R/d））
环路的列C上，并保存最大值（O（N））

我想你可以把它当作一个图形来模拟，但是现在却击败了我。

来源

2010-02-11 14:23:34 dirkgently

以下必须工作：

排序所有的时间价值和保存的开始或结束状态每一时间值。
设置numberOfCalls 0通过你的时间值（计数变量）
运行和：
- 增量NUMBEROFCALLS次，如果时间值标记为启动
- 递减NUMBEROFCALLS次，如果时间值标记为最终
- 记录过程中numberOfCalls的最大值（以及发生时的时间值）

复杂度：O（N日志（n））的排序，O（n）到所有记录

来源

2010-02-11 14:25:25 Vladimir

很简单实在的，我贴出另一种解决方案，不需要排序，我不知道它是如何来讲票价性能... – 2010-02-12 12:29:47

如何跟踪numberOfCalls的最大值？ – ygnhzeus 2013-06-04 05:15:02

@ygnhzeus，将其保存在一个单独的变量中，并在当前numberOfCalls值变得大于以前的最大值时更新它 – Vladimir 2013-06-04 08:09:49

你在很短的CallStart列表中运行。然后，对每个元素（i），你看到所有j < i如果

CallEnd[j] > CallStart[i] // put it in a map with CallStart[i] as the key and some count

休息应该是很容易。

来源

2010-02-11 14:28:44 fastcodejava

在我看来，贪婪算法会做必要的。这个问题类似于找出列车时刻表所需的平台数量。所以重叠的数量将是所需平台的数量。
callStart时间排序。开始将每个调用放入一个数组（平台）中。因此，如果调用i and (i + 1)，如果callEnd[i] > callStart[i+1]那么他们不能在同一个阵列（或平台）中放置尽可能多的第一个数组中的调用。然后重复这个过程，直到所有的呼叫都用尽。最后，阵列的数量是最大重叠数量。复杂度将为O(n)。

来源

2010-02-11 14:37:23 bhups

这是多么惊人的一些问题的解决方案有时只是蹦出一条心......，我想我可能是最简单的解决方案;）

可以代表秒钟的时间，从区域的开始（ 0）结束（600）。一个电话是一对。

Python的算法：

def maxSimultaneousCalls(calls): 
    """Returns the maximum number of simultaneous calls 
    calls : list of calls 
    (represented as pairs [begin,end] with begin and end in seconds) 
    """ 
    # Shift the calls so that 0 correspond to the beginning of the first call 
    min = min([call[0] for call in calls]) 

    tmpCalls = [(call[0] - min, call[1] - min) for call in calls] 
    max = max([call[1] for call in tmpCalls]) 

    # Find how many calls were active at each second during the interval [0,max] 
    seconds = [0 for i in range(0,max+1)] 
    for call in tmpCalls: 
    for i in range(call[0],call[1]): 
     seconds[i] += 1 

    return max(seconds)

请注意，我不知道哪个电话都是在这个时候活跃;）

但在复杂的来看，这是非常微不足道的评价：它是线性的期限通话的总时间。

来源

2010-02-12 12:28:01

以下页面有解决许多语言这个问题的例子：http://rosettacode.org/wiki/Max_Licenses_In_Use

来源

2010-02-14 15:20:00 Paddy3118

我觉得这个问题很好的解决方案的一个重要因素是要认识到每一个结束时间> =通话的开始时间和该开始时间是有序的。因此，不要在阅读整个列表和排序方面进行思考，我们只需要按照开始时间的顺序阅读，并从结束时间的最小堆中进行合并。这也解决了Sanjeev关于如何在结束时间开始之前处理结束时的评论，当它们具有完全相同的时间值时，通过从结束时间min-hep进行轮询并且当它的值是< =下一个开始时间时选择它。

max_calls = 0 
// A min-heap will typically do the least amount of sorting needed here. 
// It's size tells us the # of currently active calls. 
// Note that multiple keys with the same value must be supported. 
end_times = new MinHeap() 
for call in calls: 
    end_times.add(call.end) 
    while (end_times.min_key() <= call.start) { 
    end_times.remove_min() 
    } 
    // Check size after calls have ended so that a start at the same time 
    // doesn't count as an additional call. 
    // Also handles zero duration calls as not counting. 
    if (end_times.size() > max_calls) max_calls = end_times.size() 
}

来源

2014-12-12 09:11:50

这看起来像是一个reduce操作。类比是，每次开始通话时，当前活动通话数量都会增加1.每次通话结束时，当前通话数量将降至零。

一旦你有了活动呼叫流，你所需要的就是对它们应用最大操作。这是一个工作python2例如：

from itertools import chain 
inp = ((123, 125), 
     (123, 130), 
     (123, 134), 
     (130, 131), 
     (130, 131), 
     (130, 132),) 

# technical: tag each point as start or end of a call 
data = chain(*(((a, 'start'), (b, 'end')) for a, b in inp)) 

def r(state, d): 
    last = state[-1] 
    # if a call is started we add one to the number of calls, 
    # if it ends we reduce one 
    current = (1 if d[1] == 'start' else -1) 
    state.append(last + current) 
    return state 

max_intersect = max(reduce(r, sorted(data), [0])) 

print max_intersect

来源

2017-04-04 08:14:52

下面是Python中的工作算法

def maximumOverlap(calls): 
    times = [] 
    for call in calls: 
     startTime, endTime = call 
     times.append((startTime, 'start')) 
     times.append((endTime, 'end')) 
    times = sorted(times) 

    count = 0 
    maxCount = 0 
    for time in times: 
     if time[1] == 'start': 
      count += 1 # increment on arrival/start 
     else: 
      count -= 1 # decrement on departure/end 
     maxCount = max(count, maxCount) # maintain maximum 
    return maxCount 

calls = [ 
('2:22:22 PM', '2:22:33 PM'), 
('2:22:35 PM', '2:22:42 PM'), 
('2:22:36 PM', '2:22:43 PM'), 
('2:22:46 PM', '2:22:54 PM'), 
('2:22:49 PM', '2:27:21 PM'), 
('2:22:57 PM', '2:23:03 PM'), 
('2:23:29 PM', '2:23:40 PM'), 
('2:24:08 PM', '2:24:14 PM'), 
('2:27:37 PM', '2:39:14 PM'), 
('2:27:47 PM', '2:27:55 PM'), 
('2:29:04 PM', '2:29:26 PM'), 
('2:29:31 PM', '2:29:43 PM'), 
('2:29:45 PM', '2:30:10 PM'), 
] 
print(maximumOverlap(calls))

来源

2017-10-02 19:40:42 mythicalcoder

在时间范围列表中查找（数量）重叠

回答

相关问题