Алгоритм поезда-победителя?

Question

Это проблема из прошлой экзаменационной работы:

Пусть будет $ n $ поездов X_1,X_2 ... X_n, которые идут по параллельным путям. Поезд $ i $ начинается с позиции S[i] >= 0 и движется с постоянной скоростью V[i]. Поезд считается победителем, если существует временной интервал [t_1,t_2] с t_2 - t_1 < delta, где поезд опережает все остальные поезда. Вам нужно вывести все поезда-победители. Разработайте алгоритм O(n log n) для этого.

Поскольку требуется O(n log n), я думал о некотором подходе «разделяй и властвуй», но не смог найти подходящую подпрограмму объединения.

Answer 1

Считайте, что у вас есть две решенные подзадачи. Вы уже вычислили времена, когда победитель меняется для ваших подзадач:

0-----t0------------t1----t2-----------t3------
0--t4-----------t5------------t6---------------

Теперь, чтобы объединить это: каждый раз, когда происходит событие , сравнивайте текущего победителя из двух списков, проверяйте ихcrossing time, если он находится в текущем интервале, добавьте его в список событий.

Доказательство того, что это дает O(n log n) сложность, аналогично классической сортировке слиянием.