Determine Reachability in Train Schedule

You are given a train schedule represented as a list of train routes. Each route is a list of station names, where the element at index t is the station that train visits at absolute time t. Every train starts operating at time 0 and stops after its last listed station.

A passenger starts at station start at time 0.

The passenger may board any train at their current station at the current time, stay on that train to any later station on that same route, get off at any visited station, wait at a station for any amount of time, and transfer to another train that arrives later at the same station.

Write can_reach(schedule, start, destination) to return whether the passenger can eventually reach destination.

Constraints & Assumptions

• start and destination appear somewhere in the schedule.
• Station names are strings.
• Time is discrete and equals the route index.
• Waiting at a station is allowed.
• Traveling backward on a route is not allowed unless another listed route later visits stations in that order.

Clarifying Questions to Ask

• Can multiple trains visit the same station at the same time?
• Are all routes indexed from absolute time 0?
• Should reaching the destination at any time return true?
• Is the schedule small enough for graph search over events?

Part 1 - Model The State Space

How would you model reachability with time?

What This Part Should Cover

• A state can be represented as (station, earliest_arrival_time).
• Because waiting is allowed, arriving earlier at a station dominates arriving later.
• Need to respect route direction and train arrival times.

Part 2 - Design The Algorithm

How would you determine whether the destination is reachable?

What This Part Should Cover

• Preprocess each station to all train visits (time, route_id, index).
• Use a BFS or Dijkstra-like earliest-arrival search over stations.
• From a reachable station at time t, board any train visit at that station with visit time >= t, then mark later stations on that route reachable at their visit times.

Part 3 - Analyze Complexity And Edge Cases

What complexity and edge cases matter?

What This Part Should Cover

• Handling waiting, transfers, multiple visits to same station, repeated stations, start equals destination, unreachable reverse direction, and large schedules.
• Complexity in terms of total train visits and route lengths.