Friday, September 18, 2015

MJ [37] Cross River

Question:
A bug is trying to cross the river start from position 0 to position X. Every time bug can jump no more than the D steps (1 to D steps). Leaves will fall from the tree to the river based on schedule A. A[0] = 1 means a leaf will fall on position 1 at time 0. Need to find the earliest time that the bug can jump from position 0 to X using leaves; If there is no answer, return -1;

Example:
A = [1, 3, 1, 4, 2, 5]
X = 7 
D = 3
Answer: 3
Explanation: At time 3, there will be leaves on position 1,3, and 4; bug can jump 1 step, 3 step, and then 3 steps to cross the river;

Ref
[1] http://www.mitbbs.com/article_t/JobHunting/33055941.html
[2] http://www.mitbbs.com/article_t/JobHunting/33058417.html

No comments:

Post a Comment