亚马逊现场面试题：求解最大重叠会话数的优化方案及数据结构选型

嘿，这个亚马逊面试题可是经典的区间重叠问题，你的暴力思路虽然能解决，但确实在时间范围大或者会话数量多的时候拉胯。我来给你分享几个更高效的方案，还有适合的数据结构选择！

最优解法：排序+双指针法 #

这个方法的时间复杂度是O(n log n)，完全碾压暴力法，而且实现起来也很简洁。核心思路是：我们不需要遍历每一个时间单位，只需要关注「会话开始」和「会话结束」这两个关键事件点，通过排序和双指针来统计活跃数的变化。

具体步骤： #

1. 拆分并排序时间数组：把所有会话的开始时间提取到一个数组starts，结束时间提取到另一个数组ends，然后分别对这两个数组进行升序排序。
2. 双指针遍历统计：
   • 初始化两个指针i=0（遍历starts）、j=0（遍历ends），当前活跃会话数current=0，最大活跃数max_count=0。
   • 循环遍历直到i走完所有开始时间：
     • 如果starts[i] < ends[j]：说明有新会话开始，current += 1，更新max_count为max(max_count, current)，然后i += 1。
     • 否则：说明有会话结束，current -= 1，j += 1。

用你的示例走一遍流程： #

你的会话数据是：[[1,4],[3,5],[2,7],[5,10]]

• 排序后的starts：[1,2,3,5]
• 排序后的ends：[4,5,7,10]

1. i=0, j=0：1 < 4 → current=1，max_count=1，i=1
2. i=1, j=0：2 < 4 → current=2，max_count=2，i=2
3. i=2, j=0：3 < 4 → current=3，max_count=3，i=3
4. i=3, j=0：5 > 4 → current=2，j=1
5. i=3, j=1：5 == 5 → current=1，j=2
6. i=4（遍历完所有开始时间），循环结束，最终max_count=3，和示例答案一致。

关于数据结构的选择 #

你问的「将开始时间和结束时间分别存储在两个不同数组」绝对是最优选择之一！原因很简单：

• 排序操作只需要针对两个数组进行，时间开销是O(n log n)，这是整个算法的主要开销。
• 双指针遍历是线性的O(n)，整体效率极高。
• 相比把所有会话存在列表里再处理，拆分数组的方式更直接，减少了不必要的判断逻辑。

另外，还有一种等价的思路是事件数组法：把每个会话拆成两个事件，比如(start_time, +1)和(end_time, -1)，然后对事件数组排序（注意：如果两个事件时间相同，要把-1的结束事件排在+1的开始事件前面，避免同一时间点重复计数）。之后遍历事件数组，累加数值，记录最大值。这种方法和双指针法本质一样，只是实现形式不同，你可以根据习惯选择。

为什么暴力法效率低？ #

暴力法的问题在于如果会话的时间范围极大（比如结束时间是1e9），你根本没法遍历每一个时间单位；而且如果会话数量是n，每个时间点要检查n个会话，时间复杂度会变成O(n * max_time)，这在数据量大的时候完全不可行。而排序双指针法的时间开销只和会话数量n有关，不管时间范围多大都能高效处理。

内容的提问来源于stack exchange，提问作者M.S.