jeremymanning.md

Problem 2045: Second Minimum Time to Reach Destination

Initial thoughts (stream-of-consciousness)

• This is another graph problem (sort of a shortest path problem, but with a few differences)
• There are a few twists in this problem:
  • The red/green traffic signals are going to change how we factor in edge lengths. We'll have to come up with a way of handling this, but essentially as we traverse a path we need to use the traffic rules to figure out how long it will take.
  • Finding the "second minimum time" is a little trickier than finding the (strict) minimum time. The standard shortest path algorithms would do something like replacing (in the adjacency matrix) the distances between two vertices if a new path had a shorter distance. But now I think we need to maintain two adjacency matrices: one for the minimum distances, and one for the second minimum distances (i.e., the minimum values that are strictly greater than whatever is in the minimum distance matrix.
• Another important part of the problem is that we don't need to compute the paths between every pair of vertices, since we know that the only path that matters is from vertex 1 to vertex $n$. So instead of the Floyd-Warshall algorithm, which we used for yesterday's problem and the day before yesterday's problem, I think we should use Dijkstra's algorithm for this problem (but modified as described above). Pasting in from yesterday's notes, here is the pseudocode for Dijkstra's algorithm:

• Ok...so now we have a general approach; let's figure out how to deal with these twists.

Refining the problem, round 2 thoughts

• Handling traffic rules:
  • We know that all signals start off as green at time 0
  • Let's say that the current signal status when we reach vertex i is isGreen, and the journey from vertex i to j takes x minutes. If isGreen == True and x is between 0 and change minutes, the status doesn't change (but now we only have change - x minutes before the next transition). Alternatively, if change < x <= 2 * change, then now isGreen == False and we'll need to add y = 2 * change - x minutes to the journey from j to the next destination. (If j is the endpoint-- i.e., vertex $n$, then we don't need to pay that extra cost.)
    • If isGreen == False then we need to wait until the signal turns green (this takes y minutes, as computed above) and then we proceed as though isGreen == True.
    • Only the final (up to) 2 * change minutes of the journey matter with respect to accounting for traffic rules. I think we can compute the cost as something like x + extra, where extra is computed as follows:
      • Start with extra = 0
      • If there is time remaining until the signal turns green from the remaining journey (let's call that amount y), then extra += y. For the first journey (from vertex 1 to a neighbor) we know that y == 0.
      • Then take remainder = x % (2 * change):
        • If 0 <= remainder < change then keep track of how much less time we have on the next journey-- but we can leave the next vertex right away
        • If change <= remainder < 2 * change then we arrive when the signal is red, so on the next journey from the destination we'll need to wait 2 * change - remainder minutes to leave.
  • Ok...so these notes are a little convoluted. But what I think I'm coming to is that we're going to need to keep track of greenTimeSpent (amount of time spent traveling to the current vertex during the most recent green signal-- if the signal is green when we arrive; if we arrive when the signal is red, greenTimeSpent = 0). And we also need to keep track of timeUntilGreen-- the amount of time left until we can leave the destination vertex. But timeUntilGreen only applies if we arrive when the signal is red; otherwise (if the signal is green), then we set timeUntilGreen = 0. Then, when we're computing travel times between vertices, we want to add timeUntilGreen to the stated travel time. And then we subtractgreenTimeSpent when we need figure out the signal status upon arrival at the destination vertex.
• Finding the second minimum time:
  • In the "standard" Dijkstra's algorithm, we continually replace the path distance from i to j with alternative smaller values if/when we find them. But in the "second minimum" version, we'll need to maintain two parallel representations of the path distances:
    • The first representation is the standard minimum path distance
    • The second representation (which stores the second minimums) replaces the path distance from i to j with an alternative smaller value only if (a) it's smaller than the current distance in the second minimum representation and it's strictly greater than whatever the minimum path distance from i to j is.
• Functions to write:
  • computeTravelTime(current_time, travel_time): returns the time needed to get to the next vertex, accounting for signal status
    • Actually...travel_time is always the same, so we can just use computeTravelTime(current_time)!
  • Then we just need to implement this modified version of Dijkstra's algorithm (i.e., breadth first search) to find the second minimum time needed to get from vertex 1 to $n$.
• One potential edge case: what if there is only 1 path from vertex 1 to $n$? Then I think to get the second minimum time, we would need to double back along the trip between the nearest vertices (accounting for signal status)-- e.g., we'd need to add an extra loop (for some adjacent vertices i and j): ... --> i --> j --> i --> j --> ....

Other notes

• For each branch of the path we take, we need to track how long it took to get there and where we are "now"
• Given the current time, we can compute the current signal status and update the next travel time accordingly
• To store both the "minimum" and "second minimum" times, we can create a matrix of tuples: min_times[i][j][0] has the minimum time path from i to j, and min_times[i][j][1] has the second minimum time from i to j:
  • If we find a better time than min_times[i][j][0]:
    • min_times[i][j][1] = min_times[i][j][0]
    • min_times[i][j][0] = new_best_time
• We can use a list of lists to represent the graph:
  • graph[i] stores the edges originating at i
  • Initialize all edges to empty lists
• The travel time computation is organized around green/red cycles:
  • Each cycle takes cycle = 2 * change minutes
  • The signals start as green; each 2 * change minutes they return to green
  • If (after rounding down to the nearest multiple of change) the current time (current_time) is an odd multiple of change (i.e., the lights are currently red; (current_time // change) % 2 == 1), we need to wait until the lights turn green, which will take wait_time = cycle - (current_time % cycle) minutes. The new time is wait_time + time + current_time.
  • If (after rounding down to the nearest multiple of change) the current time (current_time) is an even multiple of change (i.e., the lights are currently green; (current_time // change) % 2 == 0), then we can leave right away (wait_time is 0), so the new time is time + current_time.

Attempted solution(s)

classSolution: defsecondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) ->int: defcomputeTravelTime(current_time): # Calculate effective travel time considering traffic lightscycle=2*changeif (current_time//change) %2==1: # lights are redwait_time=cycle- (current_time%cycle) returncurrent_time+wait_time+timeelse: # lights are greenreturncurrent_time+time# Build the graphgraph= [[] for_inrange(n+1)] foru, vinedges: graph[u].append(v) graph[v].append(u) # List to keep track of the minimum and second minimum times to each vertexmin_times= [[float('inf'), float('inf')] for_inrange(n+1)] min_times[1][0] =0# Queue for BFSqueue= [(0, 1)] # (current time, current vertex)whilequeue: curr_time, vertex=queue.pop(0) # Explore neighborsforneighboringraph[vertex]: next_time=computeTravelTime(curr_time) ifnext_time<min_times[neighbor][0]: # demote minimum time to second minimum time and update minimum timemin_times[neighbor][1] =min_times[neighbor][0] min_times[neighbor][0] =next_timequeue.append((next_time, neighbor)) elifmin_times[neighbor][0] <next_time<min_times[neighbor][1]: # update second minimum timemin_times[neighbor][1] =next_timequeue.append((next_time, neighbor)) # Return the second minimum time to reach vertex nreturnmin_times[n][1]

• Given test cases pass
• I'm out of time for thinking about this; submitting...

😌 phew!