There are N cities numbered from 1 to N, arranged in a row from left to right, and N – 1 one-way roads between them:
1 -> 2 -> 3 -> ... -> N
A plan is made to build M new roads one by one. The K-th new road connects city A[K] with city B[K]. Each road goes from a smaller city number to a larger city number. No two roads intersect.
Jack lives in city 1 and his school is in city N. After each new road is built, he wants to know the distance from home to school. The distance is the minimum number of roads required to travel between the two cities.
Write a function:
def solution(A, B, N)that, given two arrays A and B consisting of M integers each and an integer N, returns an array D consisting of M integers, where D[K] is the distance from home to school after building the first K roads.
Examples:
- Given
A = [2, 5, 1],B = [4, 7, 4]andN = 7, the function should return[5, 4, 3]. - Given
A = [1, 1, 1],B = [7, 4, 6]andN = 7, the function should return[1, 1, 1]. - Given
A = [30, 50, 40],B = [40, 60, 50]andN = 100, the function should return[90, 81, 72].
Write an efficient algorithm for the following assumptions:
Nis an integer within the range[1..100,000];Mis an integer within the range[0..100,000];- each element of arrays
AandBis an integer within the range[1..N]; A[K] < B[K]for eachKwithin the range[0..M-1];AandBhave the same length;- there are no two identical roads;
- there are no two intersecting roads.
The key idea is to maintain the current shortest path from city 1 to city N as new non-crossing forward roads are added. Initially, the distance is N – 1. Each new road may bridge part of the existing path and merge or replace some consecutive segments, so the shortest distance can only stay the same or decrease. Because the roads never intersect and always go from a smaller city to a larger one, the affected intervals can be tracked in order and updated efficiently with binary search and interval merging. This produces the distance after every insertion within the required limits.
