Region With the Fewest Reachable Peers Under a Latency Budget
Data centers are connected by weighted links. Within a fixed latency budget, find the data center that can reach the fewest others; on a tie, prefer the one with the largest id (it is the natural failover candidate).
Problem
There are n cities numbered 0..n-1 connected by weighted bidirectional edges. Given a distanceThreshold, return the city with the smallest number of other cities reachable within distanceThreshold (sum of edge weights). If several cities tie, return the one with the greatest index.
Input
An integer n, edges as [from, to, weight], and an integer distanceThreshold.
Output
An integer: the chosen city id.
Constraints
- 2 <= n <= 100
- 1 <= edges.length <= n*(n-1)/2
- 1 <= weight, distanceThreshold <= 10^4; no duplicate edges or self-loops.
Examples
Example 1
Input
n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4
Output
3
City 3 reaches only {1 via 2, 2} within 4; ties resolve to the largest id.
Example 2
Input
n = 5, edges = [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], distanceThreshold = 2
Output
0
Cities 0 and others reach at most one peer; 0 is chosen here per the worked thresholds.