在时间范围列表中查找(数量)重叠

Question

给定一个时间范围列表,我需要找到最大重叠数.

以下是一个数据集,显示了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

如果有人知道一个算法,或者能指出我正确的方向,我将不胜感激.

TIA,

史蒂夫F.

Answer 1

以下必须工作:

1. 对所有时间值进行排序,并为每个时间值保存"开始"或"结束"状态.
2. 设为numberOfCalls0(计数变量)

3. 运行您的时间值并:

   • 如果时间值标记为"开始",则增加numberOfCalls
   • 如果时间值标记为End,则减少numberOfCalls
   • 跟踪进程中numberOfCalls的最大值(以及发生时的时间值)

复杂性:O(n log(n))用于排序,O(n)用于遍历所有记录

Answer 2

一个天真的方法怎么样：

• 取最小的开始时间和最大的结束时间（这是你的范围 R）
• 取最短的调用时长——d（排序，O(nlog n)）
• 创建一个 ceil(R/d) 整数数组 C，初始化为零
• 现在，对于每个呼叫，将 1 添加到定义呼叫持续时间的单元格 O(n * ceil(R/d))
• 循环数组 C 并保存最大值 (O(n))

我想你也可以将其建模为图表并摆弄，但目前打败了我。