OA 面试真题解析：最小总延迟连接数据中心与服务器

An AWS client has brought servers and databases from data centers in different parts of the world for their application. For simplicity, let’s assume all the servers and data centers are located on a 1-dimensional line.

You have been given the task of optimizing the network connection.

Each data center must be connected to a server. The positions of data centers and servers are given in the form of arrays.

Any particular data center, center[i], can connect to any particular server destination[j].

The lag is defined as the distance between a data center at location x and a server destination at location y, i.e. |x - y|, the absolute difference between x and y. Determine the minimum lag to establish the entire network.

Example

There are n = 3 connections, the positions of data centers, center = [1, 2, 2], and the positions of the server destinations, destination = [5, 2, 4].

The most efficient deliveries are:

• The center at location 1 makes the first connection to the server at location 2.
• The center at location 2 makes the second connection to the server at location 4.
• The center at location 2 makes the third connection to the server at location 5.

The minimum total lag is abs(1 - 2) + abs(2 - 4) + abs(2 - 5) = 1 + 2 + 3 = 6.

Function Description

Complete the function getMinDistance in the editor below.

getMinDistance has the following parameter(s):

• int center[n]: the positions of data centers
• int destination[n]: the positions of server destinations

Returns

• long int: the minimum lag

Constraints

• 1 <= n <= 10^5
• 1 <= center[i], destination[i] <= 10^9

Sample Case 0

Input:

center = [3, 1, 6, 8, 9]
destination = [2, 3, 1, 7, 9]

Output:

5

Explanation:

You may create the connections as:

center = [1, 3, 6, 8, 9]
destination = [1, 2, 3, 7, 9]

Minimum total distance = abs(1 - 1) + abs(2 - 3) + abs(3 - 6) + abs(7 - 8) + abs(9 - 9) = 0 + 1 + 3 + 1 + 0 = 5.

Sample Case 1

Input:

center = [4, 6]
destination = [5, 5]

Output:

2

Explanation:

Minimum total distance = abs(5 - 4) + abs(5 - 6) = 1 + 1 = 2.

这道题的核心是把所有数据中心和服务器都看成一维数轴上的点，然后要让每个数据中心都连接到一个服务器，使总距离 |x-y| 之和最小。最优策略是分别对 center 和 destination 排序后，按相同位置一一配对，因为在一维绝对值距离下，排序匹配能保证总成本最小。实现时只需要对两个数组排序，再遍历累加对应元素差值即可，时间复杂度为 O(n log n)，适合 n 达到 10^5 的数据范围。