寻找（的数量）在时间范围的列表重叠 [英] Finding (number of) overlaps in a list of time ranges

问题描述

由于时间范围的列表，我需要找到重叠的最大数量。

Given a list of time ranges, I need to find the maximum number of overlaps.

下面是一个显示的电话有10分钟间隔的数据集，从 我想找到在有效行的最大个数 间隔。 IE浏览器。从下面的例子中，究竟是处于活动状态的同时呼叫的最大数目：

Following is a dataset showing a 10 minute interval of calls, from which I am trying to find the maximum number of active lines in that interval. ie. from the example below, what is the maximum number of calls that were active at the same time:

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还是可以在正确的方向指向我，我 将不胜感激。

If anyone knows an alogrithm or can point me in the right direction, I would be grateful.

TIA，

史蒂夫˚F

推荐答案

以下必须工作：

1. 排序所有的时间价值观并保存开始或结束状态，每次值。
2. 设置 numberOfCalls 0（计数变量）

3. 通过你的时间值运行和：

1. Sort all your time valuess and save Start or End state for each time value.
2. Set numberOfCalls to 0 (count variable)

3. Run through your time values and:

• 在增量numberOfCalls如果标记为开始时间值
• 在递减numberOfCalls如果标记为结束时间值
• （当它发生和时间值），在此过程中跟踪numberOfCalls的最大值

复杂度：O（N日志（N））进行排序，为O（n）通过所有记录运行

Complexity: O(n log(n)) for sorting, O(n) to run through all records

这篇关于寻找（的数量）在时间范围的列表重叠的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！