Assign Waiting Riders to the Earliest-Arriving Car on Fixed Routes

A map has n attractions, numbered 0 to n - 1, joined by two-way roads. roads[i] = [u, v, t] is a road between attractions u and v that takes t minutes to drive in either direction.

Several cars each drive one fixed route. routes[c] is the ordered list of attractions that car c visits. Every car leaves the first attraction of its route at time 0 and drives the route once without waiting anywhere, so it reaches each later attraction after the total driving time of the roads along its route up to that attraction.

Riders are waiting at attractions from time 0. riders[p] = [start, dest] means rider p is at attraction start and wants to reach attraction dest. Each rider takes the earliest-arriving car that can carry them there. Return which riders each car carries.

Function Signature

def assign_riders(n: int, roads: list[list[int]], routes: list[list[int]], riders: list[list[int]]) -> list[list[int]]:

Rules

• The arrival time of car c at position i of its route (0-based) is the sum, over every j < i, of the time of the road between routes[c][j] and routes[c][j + 1]. The arrival time at position 0 is 0.
• Car c can carry rider p only if start appears in routes[c] and dest appears in routes[c] at a later position.
• Among the cars that can carry rider p, the rider boards the one with the smallest arrival time at start. If several of those cars tie, the rider boards the one with the smallest index.
• A rider whom no car can carry boards no car. Cars have unlimited capacity, and riders never change cars.
• Return a list result with one list per car: result[c] holds the indices of the riders that car c carries, in increasing order. A car that carries nobody gets an empty list.

Constraints

• 2 <= n <= 10^4
• 1 <= len(roads) <= 5 * 10^4. Each road [u, v, t] has 0 <= u, v < n, u != v and 1 <= t <= 10^4, and at most one road joins any pair of attractions.
• 1 <= len(routes) <= 1000. Each route has at least 2 attractions, never visits an attraction twice, and every two consecutive attractions on it are joined by a road. All routes together hold at most 10^5 attractions.
• 1 <= len(riders) <= 10^5. Each rider [start, dest] has 0 <= start, dest < n and start != dest.
• Every arrival time is below 10^9, so it fits in a 32-bit signed integer.

Examples

Example 1

Input:  n = 5, roads = [[0, 1, 4], [1, 2, 3], [2, 3, 2], [0, 4, 1], [4, 2, 2], [1, 3, 6]], routes = [[0, 1, 2, 3], [4, 2, 1], [0, 4, 2, 3]], riders = [[0, 3], [2, 3], [2, 1], [4, 0], [1, 2]]
Output: [[0, 4], [2], [1]]

Car 0 reaches attractions 0, 1, 2, 3 at times 0, 4, 7, 9. Car 1 reaches 4, 2, 1 at times 0, 2, 5. Car 2 reaches 0, 4, 2, 3 at times 0, 1, 3, 5.

• Rider 0 (0 to 3): cars 0 and 2 both reach attraction 0 at time 0, so the tie goes to car 0.
• Rider 1 (2 to 3): car 0 reaches 2 at time 7 and car 2 at time 3, so car 2. Car 1 never reaches 3.
• Rider 2 (2 to 1): only car 1 visits 1 after 2.
• Rider 3 (4 to 0): no car visits 0 after 4, so rider 3 rides nothing.
• Rider 4 (1 to 2): only car 0 visits 2 after 1.

Example 2

Input:  n = 3, roads = [[0, 1, 5], [1, 2, 5], [0, 2, 20]], routes = [[0, 2], [0, 1, 2]], riders = [[0, 2], [1, 2]]
Output: [[0], [1]]

Both cars reach attraction 0 at time 0, so rider 0 boards car 0 by index, even though car 1 reaches attraction 2 sooner. Only car 1 visits attraction 1.

Example 3

Input:  n = 2, roads = [[0, 1, 7]], routes = [[1, 0]], riders = [[0, 1]]
Output: [[]]

The car visits attraction 1 before attraction 0, so it cannot take the rider from 0 to 1.

Board Riders onto the Earliest Fixed-Route Car

Hints

1. Each car's timetable is fixed: work out when every car reaches each attraction on its own route, remembering that it is at its first attraction at time 0.
2. A car qualifies only when the rider's destination appears later than the start on that car's route, so the car that reaches the start first may still be unable to carry the rider.
3. The choice depends only on the arrival time at the start and then the car index; when the car reaches the destination does not matter.

Approach

Index every road time by ordered attraction pair, in both directions. Drive each car once along its route, keeping a running arrival time that is 0 at position 0 and adds the road time of each consecutive pair. For every car record the position of each attraction it visits, and append (arrival time, car index, position) to that attraction's visit list. Sort each visit list by arrival time, then car index. For each rider in increasing index, walk the visit list of start in that order and stop at the first car whose route contains dest at a position greater than the start position; append the rider to that car's list.

Correctness: the sorted visit list of start is exactly the preference order the rules define (smallest arrival time at start, ties broken by smallest car index). A route never repeats an attraction, so each car appears in that list at most once and has a unique position for every attraction it visits. The first car in that order that passes the eligibility test is therefore precisely the car the rider boards. Riders are processed in increasing index, so every car's list is already in increasing order. Only the arrival time at start is compared; the time a car reaches dest never matters.

Edge cases: a rider whose start or dest lies on no route, whose dest appears only before start, or whose start and dest lie on different routes boards nothing; a car that carries nobody keeps an empty list; roads that no route uses are never consulted; all times are exact integers below 10^9.

• Time complexity: O(R + A log A + P * K), where R = len(roads), A = total attractions over all routes, P = len(riders) and K = the largest number of routes that visit one attraction
• Space complexity: O(n + R + A + P)