题目重点:OA 题给发车时刻与当前时间,找最近一班已经发走的列车并返回分钟差;澄清当日无车与跨日。
题意与假设
这道练习题保留了面经中值得训练的核心约束,并将需要澄清的条件单独列出。现场拿到变体时,先和面试官确认这些条件。
- 训练版同一天 00:00–23:59,发车时刻可无序,当前时刻 t 允许选择 departure≤t;若还没有发车返回 -1。
- 时间格式 H:MM/HH:MM 解析为 60H+M,并校验 0≤H<24、0≤M<60;原题具体格式需确认。
- 同一时刻多班车不影响最小分钟差;跨天循环班次另作追问。
解题路线
- 先把时刻从字符串转整数分钟,避免直接按文本比较(`3:20` 与 `12:00` 字符序错误)。
- 若只问一次,单扫所有发车时刻,取所有 ≤current 的最大值 last;无 last 返回 -1,否则 current−last。
- 若同一时刻表回答很多次查询,预排序并用 upper_bound(current)−1 找最后一个 ≤current 的位置,单次 O(log n)。
- 测试 3:40→20、恰好 3:20→0、首班之前→-1、乱序/重复时刻与跨日边界。
手动走一遍
发车 [1:10,3:20,5:20] 转 [70,200,320],当前 3:40=220;不晚于 220 的最大时刻为 200,差 20。若当前 0:30=30,主训练版没有当日已发车,返回 -1;跨日版可能选前日末班,不能擅自代入。
规模与取舍
单查询 O(n) 时间、O(1) 附加空间;多查询预排序 O(n log n) 时间、O(n) 存储(若复制),每次二分 O(log n)。
易错点与追问
容易失分的边界
- 选最近将要发车的 5:20,而不是最近已发的 3:20。
- 按字符串排序时未补零导致时刻顺序错。
- 恰好发车时误排除 `=`。
- 未确认跨日却自动取前一天末班。
继续深挖
- 跨日循环班次如何计算?
- 不同日期/时区怎样表示?
- 实时延误信息加入后如何维护查询?
