Decide If a Passenger Can Reach a Station Using Time-Indexed Train Routes and Transfers

A train schedule is a collection of trains moving between stations, where stations are named by strings. Time starts at 0. Each train is given as a list of stations, and the index in the list is the time at which the train is at that station: train j is at station schedule[j][t] at time t.

A passenger starts at station start at time 0. The passenger can ride trains, get off at any station, wait there, and board another train later. Return whether the passenger can reach station dest.

Function Signature

def can_reach(schedule: list[list[str]], start: str, dest: str) -> bool:

Rules

• Train j is at schedule[j][t] for 0 <= t < len(schedule[j]), and is out of service after its last index.
• At time t, a passenger at station s may either wait at s until time t + 1, or board any train j with schedule[j][t] == s and t + 1 < len(schedule[j]), arriving at schedule[j][t + 1] at time t + 1.
• On arriving, the passenger may stay on the same train or get off. Changing trains at the same station at the same time takes no time. Waiting at a station has no time limit.
• A train may stay at a station for several time steps, or visit a station more than once.
• Return True if the passenger can be at dest at some time, and False otherwise. If start == dest, return True.

Constraints

• 1 <= len(schedule) <= 1000
• 1 <= len(schedule[j]) <= 1000, and the total length of all trains is at most 2 * 10^5
• Station names consist of 1 to 10 uppercase English letters.
• start and dest are station names. Either may be absent from every train.

Examples

Example 1

Input:  schedule = [["A", "B", "C", "D", "E"], ["O", "B", "G", "H", "Z"]]
        start = "A", dest = "Z"
Output: True

Ride the first train from A at time 0 to B at time 1. The second train is also at B at time 1, so change trains there and ride to Z, arriving at time 4.

Example 2

Input:  schedule = [["A", "B", "C"], ["B", "D"]]
        start = "A", dest = "D"
Output: False

The second train leaves B after time 0, but the passenger cannot be at B before time 1.

Example 3

Input:  schedule = [["A", "B"], ["X", "Y", "B", "D"]]
        start = "A", dest = "D"
Output: True

Arrive at B at time 1, wait until time 2, board the second train at B, and reach D at time 3.

Train Schedule Reachability with Transfers

Hints

1. Waiting has no time limit, so once the passenger can be at a station at some time, they can also be there at every later time.
2. Boarding at time t requires being at the station by time t; a station first reached at time t + 1 cannot be used to board at time t.
3. Staying on a train for another step is the same as getting off and boarding it again, since the train is at that station and still has a next index.

Approach

Because waiting has no time limit, the set of stations the passenger can occupy only grows over time: if the passenger can be at station s at time t, they can be at s at every later time. Staying on a train for one more step is equivalent to getting off and boarding the same train again, because the train is at that station and still has a next index exactly when riding on is allowed. So it suffices to track R(t), the set of stations the passenger can be at by time t. R(0) = {start}, and R(t + 1) is R(t) plus schedule[j][t + 1] for every train j with t + 1 < len(schedule[j]) and schedule[j][t] in R(t). By induction on t, R(t) is exactly the set of stations the rules let the passenger be at at time t: every move is a wait (kept by R growing) or a one-step ride from a station in R(t), and every such ride is added. The implementation simulates t = 0, 1, 2, ...; at each step it first collects all arrivals and only then adds them, so a station first reached at time t + 1 is never used to board at time t. Trains are sorted by length in descending order, so the trains still able to depart at time t (length greater than t + 1) form a prefix that only shrinks; each step scans only that prefix, so the total scanning work is at most the total length of all trains. The search returns True as soon as dest is added (or immediately when start == dest) and False once no train has a next index. Edge cases: start or dest absent from every train, length-1 trains (never boardable), a station at a train's last index (no boarding there), dwelling and revisited stations, and same-time transfers.

• Time complexity: O(n log n + L), where n is the number of trains and L is the total length of all trains
• Space complexity: O(n + L)