Add Range-Powering Stations to Raise the Weakest City
Company: Teradata
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
### Problem
City i initially contains stations[i] power stations. A station supplies every city within index distance r, clipped to the array boundaries. Build k more stations at arbitrary cities, allowing several at one city, and return the largest achievable minimum city power as long long.
```cpp
class Solution {
public:
long long maxPower(vector<int>& stations, int r, int k);
};
```
### Examples
**Example 1:**
```text
Input: stations = [0,0,0], r = 1, k = 1
Output: 1
Explanation: Put the new station at the middle city so all three cities receive power.
```
**Example 2:**
```text
Input: stations = [2,2], r = 0, k = 1
Output: 2
Explanation: With no range, one added station cannot raise both cities above 2.
```
### Constraints
- `1 <= stations.length <= 100000`.
- `0 <= stations[i] <= 100000`.
- `0 <= r <= n-1`; `0 <= k <= 10^9`.
### Clarifying Questions
- Does power count stations or cities? Count all stations whose range covers the city.
- Can several new stations be built at one city? Yes.
- Does a station cover its own city? Yes.
- What happens at an array boundary? Coverage stops there; cities do not wrap around.
```hint Check the boundary
Check range zero and a range large enough for a station to cover every city.
```
Overview: Place additional power stations to maximize the weakest city’s power, with each station supplying every city within a fixed index distance.