PROBLEM LINKS
DIFFICULTY
EASY
PREREQUISITES
Binary Search, Dynamic Programming, Graph Theory
PROBLEM
You are given N bus stations and M buses that run between these bus stations. Each bus is described as
( start station, end station, start time, end time )
Now, you wish to travel from station 1 to station N. While doing so, you may have to wait before boarding a bus, because you reached the bus station from which you wish to catch the next bus, earlier than the time the bus arrives at.
You wish the find a strategy for taking buses such that the longest wait time spent between un-boarding a bus and boarding the next bus, is as small as possible.
Also, you must reach N within time T. So do not consider schedules that make you reach N after time T.
QUICK EXPLANATION
We note that the answer needed, the maximum wait time in the optimal schedule (that minimizes the maximum wait time) satisfies the following property
If there is a schedule in which the wait time is never more than x, then there is a schedule in which the wait time is never more than x + y, for any positive y
This hints us at the possibility of binary searching over the answer.
Thus, if we fix how long we are going to wait - say W - we can test whether there is a way to reach N before time T, or not - while never waiting for more than W units of time.
EXPLANATION
How do you determine if it is possible to reach N, within time T, while never waiting for more than W units of time?
Consider a graph G, whose vertices are defined by the pair (u,x)
- u is the label of a bus station
- x is the time stamp between 0 and T
A vertex in this graph represents whether a bus station u could be reached at time x, or not, by finding its reachability from (1,0). The edges in this graph are determined by the buses and our threshold for wait.
The number of vertices in the graph are potentially 1014. This is of course an impossible number to consider. But, there are some insights that help
- You can only reach a new station by using some bus
- If you can reach (u,x), after using some bus
- you can reach (u,x+w) also
- where 1 ≤ w ≤ W
Thus, the only (u,x) pairs we need to store are (1,0) - the initial position - and those defined by some or the other bus. Thus, O(W) vertices only.
Our algorithm now looks like a breadth first search. If we sort the buses by start times, we can parse through the buses exactly once and be assured that any possible strategy has been considered (since any strategy will be a ordered subset of this ordered set of buses).
Let us talk about the implementation of the above ideas.
We can maintain a set of times at which bus station u can be reached by using a bus, for each u. Let this be denoted by S(u).
S(1) = {0}
S(k) = ∅, for all k ≠ 1
For some bus ( start-station, end-station, start-time, end-time )
- Search for a t in S(start-station) such that
- t ≤ start-time
- start-time - t ≤ W
This way we can insert end-time in S(end-station) if such a t is found. This of course denotes the reachability of (end-station, end-time).
The result (yes / no) will depend upon whether the smallest value in S(N) is smaller than T, or not.
S(k) should be a data structure that supports efficient insertion and search. Using a self balanced tree (such as set in C++) is enough. Alternately, you can use the following trick
Sort the buses by end-time instead of start-time
We note that any strategy of bus selections will still be an ordered subset of this ordered set of buses.
The additional benefit we get is that S(k) can be simple arrays. Any new insert in S(k) is a simple append, because all new end-times are larger than the previous end-times. We can use standard binary search in the search step above.
The complexity of the algorithm still remains the same, but this solution will most probably have smaller constants.
The expected complexity of the solution is O(M log M log T).
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.