台积电 OA 面试真题解析：Latency Analysis（最小化网络最大延迟）

Latency Analysis

Divide a network of data centers into optimal local regions.

Given a network of g_nodes data centers and g_edges bidirectional connections, the i-th connection connects data centers g_from[i] and g_to[i] with a latency of g_weight[i]. The max-latency of a network is the maximum latency of any connection.

Divide this network into k or fewer networks by removing some of the connections such that the maximum latency of all the regions are minimized. Find the minimum possible value of the maximum max-latency of the networks formed.

Complete the function getMinMaxLatency.

The function accepts following parameters:

• INTEGER g_nodes
• INTEGER_ARRAY g_from
• INTEGER_ARRAY g_to
• INTEGER_ARRAY g_weight
• INTEGER k

Returns:

• INTEGER: the minimum possible value of the maximum max-latency of the networks formed.

Sample Input For Custom Testing

5
1
2
3
1
2
1

Sample Output

3

Explanation

The network can be split so that the maximum latency among the resulting regions is 3.

这道题本质上是在一张带权连通图里，通过删除若干边把网络切成不超过 k 个连通块，并让所有连通块中“最大边权”的最大值尽量小。标准做法是把边按权重从小到大排序，然后用并查集逐步合并；当当前连通块数量已经降到 k 时，下一条会让两块合并的最小权重，就是答案。它和最小生成树很接近，核心是利用“先保留更小的边”来最小化分组后的最大延迟，时间复杂度主要来自排序，适合处理大规模数据中心网络。