Katkat
Back

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

GleanMachine Learning Engineer · Onsite
MediumMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

Given trains described as time-indexed lists of stations, decide whether a passenger starting at one station at time zero can reach another by riding, waiting and transferring. Tests modeling station and time as search states, handling waits and same-time transfers, and breadth-first search over a time-expanded graph.

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.