Python Code on Their Laptop

Torc Robotics needs to route an autonomous vehicle through a directed road network while accounting for temporary road closures. Given the vehicle's start time, compute the earliest possible arrival time at a destination. The vehicle may wait at any intersection, and a road can be used only if it remains open for the entire traversal.

Implement earliest_arrival(graph, closures, start, goal, start_time).

Formal Specification

• graph is a dictionary mapping each node to a list of [neighbor, travel_time] pairs.
• closures maps a directed edge string, formatted as "u->v", to sorted, non-overlapping closure intervals [open_start, open_end]. Each interval uses half-open semantics: the road is closed at times open_start <= t < open_end.
• start, goal, and node identifiers are strings.
• start_time is a nonnegative integer.
• Return the earliest integer arrival time at goal, or -1 if the destination is unreachable.

A vehicle may depart an edge at any integer time at or after its current arrival time. Waiting is allowed. A traversal [departure, departure + travel_time) must not intersect a closure interval.

Examples

Example 1: graph = {"A":[["B",4],["C",2]],"B":[["D",3]],"C":[["D",6]],"D":[]}, closures = {"A->B":[[3,10]]}, start = "A", goal = "D", start_time = 0
Output: 9
The direct route through B must wait until time 10, arriving at 13. The route through C arrives at 2 + 6 = 8, but the earliest safe route considering the closure is 8.

Example 2: graph = {"A":[["B",5]],"B":[]}, closures = {"A->B":[[0,20]]}, start = "A", goal = "B", start_time = 0
Output: 20
The vehicle waits until the closure ends, then reaches B at time 25. Therefore the correct output is 25.

Constraints

• 1 <= number of nodes <= 10^5
• 0 <= number of directed edges <= 2 * 10^5
• Travel times are positive integers.
• Closure intervals for each edge are sorted and non-overlapping.