This is a problem from a past exam paper:
Let there be $n$ trains X_1,X_2 ... X_n all which run along parallel tracks. Train $i$ starts from position S[i] >= 0 and runs at constant speed V[i]. A train is said to be a winner if there exists a time interval [t_1,t_2] with t_2 - t_1 < delta where the train is ahead of all other trains. You need to output all the winner trains. Design an O(n log n) algorithm for this.
As a O(n log n) is required, I was thinking of some divide and conquer approach, but couldn't find the appropriate combine subroutine.
Consider you have two subproblem solved. You have already computed times where winner are changing for your subproblems:
0-----t0------------t1----t2-----------t3------
0--t4-----------t5------------t6---------------
Now to merge this: each time an event occurs, compare the current winner from the two lists, check their crossing time, if it's in the current interval add it to the event list.
The proof that this gives O(n log n) complexity is the same as the classic merg sort.