Google 面试题 #9 — 区间用户活动表格合并 – 谷歌面经 – 谷歌挂经 – 面试辅助 – 代面试 – 面试狗

You are given a list of users, each with a start time and an end time.
For each time interval where the set of active users changes, output:

• the interval start
• the interval end
• the list of users active during that interval

Input Example

Name   | Start | End
-------|-------|-----
Abby   | 10    | 100
Ben    | 50    | 70
Carla  | 60    | 120
David  | 150   | 300

Output Example

Start | End | Names
------|-----|-------------------------
10    | 50  | Abby
50    | 60  | Abby, Ben
60    | 70  | Abby, Ben, Carla
70    | 100 | Abby, Carla
100   | 120 | Carla
150   | 300 | David

核心思路

将所有用户的开始、结束时间转成「事件点」：

• (time, +user) 表示用户加入
• (time, -user) 表示用户离开

然后对所有事件按时间排序， 扫描线遍历（sweep line）：

• 每遇到开始事件，把用户加入 active set
• 每遇到结束事件，把用户从 active set 移除
• 两个事件点之间形成一个区间，当前 active set 就是该区间的活跃用户列表

最终输出所有不为空的区间与对应的用户。

VOprep 团队长期陪同学员实战各类大厂 OA 与 VO，包括 OpenAI、Google、Amazon、Citadel、SIG 等，提供实时答案助攻、远程陪练与面试节奏提醒，帮助大家在关键时刻不卡壳。
如果你也在准备 Stripe 或类似工程向公司，可以了解一下我们的定制助攻方案——从编程面到系统设计，全程护航上岸。