如何求一天内最大在线人数及维持最大人数的最长时间？

日期：2026-07-12
标签：#面试 #八股 #后端 #扫描线 #算法 #场景题

一句话答案

把每条登录区间转换为登录时刻 +1、登出时刻 -1，按秒聚合后扫描前缀和；人数在相邻事件时间区间内恒定，据此求最大值并合并最大值的连续区间。

面试口语版

先定义在线区间为 [login, logout)。每条日志生成两个事件，登录秒加一、登出秒减一，相同秒先聚合净变化。按时间升序扫描，在时间 t 应用 delta 后，得到区间 [t,nextTime) 的在线人数。如果大于历史最大值，就更新最大值并把最长持续时间设为该区间长度；等于最大值时，如果与上一最大区间连续就合并，否则单独计算。一天只有 86400 秒，也可以直接用长度 86401 的差分数组，复杂度 O(n+86400)，不需要排序。

差分算法

diff[login]  += 1
diff[logout] -= 1
online += diff[t]
online 在 [t, t+1) 内有效

关键细节

明确登出秒是否仍算在线，决定区间开闭。
跨天会话要裁剪到当天 [0,86400)。
无事件的秒也要计入持续时间，差分数组最方便。
“最长持续时间”是连续区间，多个分散峰值不能直接相加。

面试官追问

相同秒登录和登出如何处理？
为什么一天场景用差分数组更简单？
如何输出最长峰值区间的起止时间？

面试官追问参考答案

1. 相同秒登录和登出如何处理？

在 [login,logout) 语义下，把同一秒所有增减先聚合，再计算该秒开始后的在线人数；登出者不计入该秒新区间，登录者计入。若业务采用闭区间，处理规则需相应改变。

2. 为什么一天场景用差分数组更简单？

时间粒度固定为秒，值域只有 86400，数组空间很小且无需对 2n 个事件排序。写差分 O(n)，扫描固定 86400 次即可得到人数和连续区间。

3. 如何输出最长峰值区间的起止时间？

扫描时记录当前最大连续段 currentStart；人数进入最大值时开始，离开时计算 [currentStart,t) 长度并更新最佳起止。若发现更高最大值，清空旧结果并从当前秒重新统计。

学习清单

掌握扫描线和差分数组。
能处理开闭区间、跨天和连续峰值。