# Find a strategy to evade hungry lions on the real line for the longest time

This is an interview question I was asked, which I don't know how to approach. I would appreciate pointers to algorithms I should look up.

You are placed on the real line, and there also are $$K$$ lions on the real line, which are currently sleeping. You are given the wake up time of each lion. You can walk past a lion as long as it is sleeping. As soon as any lion wakes up, it starts walking towards you to eat you. Both you and the lions can walk at a maximum speed of 1m/s.

Given your starting position and the starting positions and wake up times of the lions, find the maximum time you can stay alive (can be infinite), and the strategy you should follow.

• How slow the lions are! – xskxzr Nov 18 '18 at 5:55
• I'm fairly sure that this is a question for the purpose of observing you tinker, not for seeing how many solutions you know by heart. – Raphael Nov 18 '18 at 11:33
• Based on gnasher729's answer, I believe that a cleaner solution should be "move to some point $X$ and wait there until you are hit by two lions from different directions". What is the actual (fast) algorithm to find $X$? – Apass.Jack Nov 19 '18 at 6:01

Assume you start at zero. Lion #i is at $$d_i$$ and wakes up at $$w_i$$. If there is no lion with $$d_i > 0$$ and $$w_i < d_i$$ then you walk to the right and are safe. If there is no lion with $$d_i < 0$$ and $$w_i < |d_i|$$ then you walk to the left and are safe.
Otherwise, you die. There is always an optimal strategy of the form "move to some point X and stop, then wait until lions force you to move, and die when two lions from either side meet" - the point X is obviously not known. The point X is limited; if for example $$d_i > 0$$ and $$w_i < d_i$$ then you can walk only $$(d_i + w_i)/2$$ before you are forced back.