SWE · 70 分钟 OA

Capital One 最近已发列车:时刻表查询与分钟差

OA 题给发车时刻与当前时间,找最近一班已经发走的列车并返回分钟差;澄清当日无车与跨日。

题目重点:OA 题给发车时刻与当前时间,找最近一班已经发走的列车并返回分钟差;澄清当日无车与跨日。

题意与假设

这道练习题保留了面经中值得训练的核心约束,并将需要澄清的条件单独列出。现场拿到变体时,先和面试官确认这些条件。

  • 训练版同一天 00:00–23:59,发车时刻可无序,当前时刻 t 允许选择 departure≤t;若还没有发车返回 -1。
  • 时间格式 H:MM/HH:MM 解析为 60H+M,并校验 0≤H<24、0≤M<60;原题具体格式需确认。
  • 同一时刻多班车不影响最小分钟差;跨天循环班次另作追问。

解题路线

  1. 先把时刻从字符串转整数分钟,避免直接按文本比较(`3:20` 与 `12:00` 字符序错误)。
  2. 若只问一次,单扫所有发车时刻,取所有 ≤current 的最大值 last;无 last 返回 -1,否则 current−last。
  3. 若同一时刻表回答很多次查询,预排序并用 upper_bound(current)−1 找最后一个 ≤current 的位置,单次 O(log n)。
  4. 测试 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。
  • 按字符串排序时未补零导致时刻顺序错。
  • 恰好发车时误排除 `=`。
  • 未确认跨日却自动取前一天末班。

继续深挖

  • 跨日循环班次如何计算?
  • 不同日期/时区怎样表示?
  • 实时延误信息加入后如何维护查询?
✓已复制微信号!