TikTok Server Network Optimization
TikTok● MediumINTERNOAProblem statement
TikTok has installed n servers on a grid. Server j is located at (x[j], y[j]).
The cost of directly connecting servers i and j is:
min(|x[i] - x[j]|, |y[i] - y[j]|)
Build a network in which every server can communicate with every other server, either directly or through intermediate servers. Return the minimum possible total connection cost.
Function
minCostToConnectServers(x: int[], y: int[]) → intExamples
Example 1
x = [2, 4, 8]y = [6, 10, 9]return = 3To connect the servers, here's the strategy:
- Connect the first and second servers: The servers are at (2, 6) and (4, 10). The cost is calculated as min(|2 - 4|, |6 - 10|) = 2.
- Connect the second and third servers: The servers are at (4, 10) and (8, 9). The cost is min(|4 - 8|, |10 - 9|) = 1.
- Connect the first and third servers: The servers are at (2, 6) and (8, 9). The cost is min(|2 - 8|, |6 - 9|) = 3. However, we already have a cheaper way to connect them indirectly through the second server.
So, the optimal way to connect the first and second servers for 2, and then the second and third servers for 1. Thus, the total minimum cost is 2 + 1 = 3.
Constraints
2 ≤ n ≤ 10^5x.length = y.length = n0 ≤ x[i], y[i] ≤ 10^9- Multiple servers may have the same coordinates.