获胜者火车的算法？
Algorithm for winner trains?
这是过去试卷中的一道题：
假设有 $n$ 列火车 X_1,X_2 ... X_n，所有这些火车都 运行 沿着平行轨道。火车 $i$ 从位置 S[i] >= 0 和 运行s 以恒定速度 V[i] 开始。如果存在 [t_1,t_2] 和 t_2 - t_1 < delta 的时间间隔，其中火车领先于所有其他火车，则火车被认为是赢家。您需要输出所有获胜者列车。为此设计一个O(n log n)算法。
由于需要 O(n log n)，我正在考虑一些分而治之的方法，但找不到合适的合并子例程。
假设您已经解决了两个子问题。您已经计算了获胜者为您的子问题改变的时间：
0-----t0------------t1----t2-----------t3------
0--t4-----------t5------------t6---------------
现在合并：每次 事件 发生时，比较两个列表中的当前获胜者，检查他们的 crossing time，如果它在当前间隔内添加它到事件列表。
这给出 O(n log n) 复杂性的证明与经典归并排序相同。
这是过去试卷中的一道题：
假设有 $n$ 列火车 X_1,X_2 ... X_n，所有这些火车都 运行 沿着平行轨道。火车 $i$ 从位置 S[i] >= 0 和 运行s 以恒定速度 V[i] 开始。如果存在 [t_1,t_2] 和 t_2 - t_1 < delta 的时间间隔，其中火车领先于所有其他火车，则火车被认为是赢家。您需要输出所有获胜者列车。为此设计一个O(n log n)算法。
由于需要 O(n log n)，我正在考虑一些分而治之的方法，但找不到合适的合并子例程。
假设您已经解决了两个子问题。您已经计算了获胜者为您的子问题改变的时间：
0-----t0------------t1----t2-----------t3------
0--t4-----------t5------------t6---------------
现在合并：每次 事件 发生时，比较两个列表中的当前获胜者，检查他们的 crossing time，如果它在当前间隔内添加它到事件列表。
这给出 O(n log n) 复杂性的证明与经典归并排序相同。