Google OA 面试真题解析：区间重叠姓名表（Interval Name Overlap Table）

You are given a table of people with three columns: Name, Start, and End. Each row represents an interval for a person.

Create a second table with columns Start, End, and Names. The output table should break the timeline into consecutive intervals using every unique start and end value from the input. For each interval, list all names whose original intervals cover that entire segment.

Example:

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

Output:

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

这道题本质上是“区间切分 + 区间覆盖查询”。先收集所有人的开始和结束时间，把这些边界按时间排序后，相邻边界之间就形成了一段段不重叠的小区间。对于每个小区间，只要检查哪些人的原始区间完整覆盖了它，就把这些名字按题目要求输出到 Names 列中。实现时可以直接用排序后的边界做扫描，复杂度主要取决于边界数量和区间数量；如果数据量较大，也可以用扫描线或事件排序来优化。