# A number of points on a line, with initial positions and speeds - find a minimum time that any two points meet

How can I compute the minimum time for two points to meet in $$O(N)$$ time?

All I can think is to compute the time for all the point pairs and get the minimum.

Can anyone give me some hints?

I'm assuming we're given an ordered list $$(y_0,y_1,...,y_{n-1})$$ of initial point positions together with a list $$(s_0,s_1,...,s_{n-1})$$ of their speeds.
You can visualize moving points on a Cartesian plane with "position" and "time" coordinate axes - so the point $$P_i$$ trace will be a ray $$R_i$$, beginning at the point $$(0,y_i)$$ and consisting of points $$(t, y_i+s_it)$$ for $$t\ge0$$. If points $$P_i$$ and $$P_j$$ meet at some time $$t$$ then their corresponding rays $$R_i$$ and $$R_j$$ will intersect, and their intersection point will be $$(t,y)$$ - we'll call this time $$t$$ a meeting time.
Observation. If an intersection point $$(t,y)$$ for two rays $$R_i$$ and $$R_j$$ has a minimal meeting time $$t$$ among all the pairs $$(i,j)$$ where $$i\lt j$$, then $$i=j-1$$ (in other words - points $$P_i$$ and $$P_j$$ were initially neighbor ones - try to prove that).
So, it means that you can look for minimal meeting time among pairs of neighbor points only - their total number is $$O(n)$$, and the algorithm time is also linear. If the original list of points is not ordered by their coordinates, then the algorithm time will include sorting, which is $$O(n\log(n))$$.