Decide If a Passenger Can Reach a Station Using Time-Indexed Train Routes and Transfers
Company: Glean
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
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
```python
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**
```text
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**
```text
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**
```text
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.
Overview: 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. Implement `can_reach(schedule, start, dest)`, which returns whether the passenger can reach station `dest`.
**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`.
The input contains no numeric values: every station is a string, and the result is a boolean (`true`/`false` in JavaScript, Java and C++).
**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.
**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.
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
Input: ([['A']], 'A', 'A')
Expected Output: True
Explanation: Minimum valid: one length-1 train and start == dest, so the answer is True without riding.
Input: ([['B', 'C']], 'Q', 'Q')
Expected Output: True
Explanation: start == dest returns True even though Q is absent from every train.
Hints
- 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.
- 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.
- 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.