Experian OA 面试真题解析：Road Network Shortest Path After Each New Road

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] and N = 7, the function should return [5, 4, 3].
• Given A = [1, 1, 1], B = [7, 4, 6] and N = 7, the function should return [1, 1, 1].
• Given A = [30, 50, 40], B = [40, 60, 50] and N = 100, the function should return [90, 81, 72].

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [1..100,000];
• M is an integer within the range [0..100,000];
• each element of arrays A and B is an integer within the range [1..N];
• A[K] < B[K] for each K within the range [0..M-1];
• A and B have the same length;
• there are no two identical roads;
• there are no two intersecting roads.

这题的核心是维护从 1 到 N 的最短路径长度，初始时答案就是 N-1。每加入一条新路 A[K] -> B[K]，本质上是在若干连续路段之间建立了一条“捷径”，可能会把原来被分开的区间合并起来，从而缩短整条路径。由于所有新路都从小编号指向大编号，而且没有交叉，区间可以按顺序维护；每次插入时用有序结构找到受影响的区间并合并，实时更新当前最短路径长度即可。这样就能在 M 次更新中高效输出每一步的答案，适合用平衡树 / 有序列表配合二分来实现。