#1620
Coordinate With Maximum Network Quality
expert · 1070 · lc medium +32 · verified · 39.3% accepted · 92 likes · top 19%
Description
You are given an array of network towers where towers[i] = [xi, yi, qi] has a position and quality factor. A tower at distance d contributes signal quality floor(qi / (1 + d)) to any coordinate within radius. Find the integer coordinate [cx, cy] that maximizes total network quality. Break ties by returning the lexicographically smallest coordinate.
Example 1:
Input: towers = [[1,2,5],[2,1,7],[3,1,9]], radius = 2
Output: [2,1]
Explanation: At coordinate (2, 1) the total quality is 13.
- Quality of 7 from (2, 1) results in ⌊7 / (1 + sqrt(0)⌋ = ⌊7⌋ = 7
- Quality of 5 from (1, 2) results in ⌊5 / (1 + sqrt(2)⌋ = ⌊2.07⌋ = 2
- Quality of 9 from (3, 1) results in ⌊9 / (1 + sqrt(1)⌋ = ⌊4.5⌋ = 4
No other coordinate has a higher network quality.
Example 2:
Input: towers = [[23,11,21]], radius = 9
Output: [23,11]
Explanation: Since there is only one tower, the network quality is highest right at the tower's location.
Example 3:
Input: towers = [[1,2,13],[2,1,7],[0,1,9]], radius = 2
Output: [1,2]
Explanation: Coordinate (1, 2) has the highest network quality.
Code
1
2
3