My solution runs in O(N logN) and it uses heap data structure. The discussion forums hint that there may be a O(N) time solution. Is there a linear time algorithm?

heap?:D
just use lower_bound

And, BTW, Yes there is.
At first I used Binary Search on each station but on the next station you can start with the previous index. code:


int canReach1 = A[i] + L1;
while (ind1 <= end && A[ind1] <= canReach1) ind1 ++;

i've used dp (which is easy to notice) with some optimization. suppose we have three stations

s1 s2 s3

and there exists path s1-s2 covered with l1, and path s1-s3 also covered with l1. then we can skip the analysis from s2. we can easily reduce used time if we create list of "allowed" stations to analyze (like s3)