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_nodesINTEGER_ARRAY g_fromINTEGER_ARRAY g_toINTEGER_ARRAY g_weightINTEGER 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
1Sample Output
3Explanation
The network can be split so that the maximum latency among the resulting regions is 3.
This problem asks you to split a connected weighted graph into at most k components while minimizing the largest edge weight inside any component. The key idea is to process edges in ascending order and use a disjoint set union structure to merge components greedily, stopping when the number of components reaches k. The next edge that would merge two remaining components gives the minimum achievable maximum latency. It is essentially a Kruskal-style clustering problem.
