2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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))$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.