Earliest Train Arrival
MediumGraphs ยท Google
Given a timetable trains, where each train is [from_station, to_station, departure, arrival], return the earliest time you can be at station target when you start at station source at time start_time. Return -1 if target cannot be reached.
You can board a train if you are at its from_station at a time no later than its departure. Waiting is free and changing trains takes no time, so a train arriving at time t can be followed by one departing at t. If source == target, the answer is start_time.
Example 1
- Input:
- trains = [[0, 1, 5, 8], [1, 2, 8, 12], [0, 2, 6, 20], [1, 2, 9, 10]], source = 0, target = 2, start_time = 0
- Output:
- 10
- Explanation
- Ride 0 to 1 and arrive at 8, then take the train departing at 9 and arriving at 10. The train departing at 8 arrives later.
Example 2
- Input:
- trains = [[0, 1, 4, 7], [1, 2, 7, 9]], source = 0, target = 2, start_time = 4
- Output:
- 9
- Explanation
- Both boundaries are inclusive: boarding at time 4 and connecting at time 7 are allowed.
Example 3
- Input:
- trains = [[0, 1, 2, 5], [1, 2, 4, 9]], source = 0, target = 2, start_time = 0
- Output:
- -1
Constraints
0 <= trains.length <= 2 * 10^50 <= from_station, to_station, source, target <= 10^50 <= start_time <= 10^90 <= departure < arrival <= 10^9