*Minimum Light Radius*

Description

You are given a list of integers nums representing coordinates of houses on a 1-dimensional line. You have 3 street lights that you can put anywhere on the coordinate line and a light at coordinate x lights up houses in [x - r, x + r], inclusive. Return the smallest r required such that we can place the 3 lights and all the houses are lit up.

Constraints:

• n ≤ 100,000 where n is the length of nums

Example 1

Input

nums = [3, 4, 5, 6]

Output

0.5

Explanation

If we place the lamps on 3.5, 4.5 and 5.5 then with r = 0.5 we can light up all 4 houses.

---

Intuition

High-precision binary search

1. Radius from 0 to the farthest house.

2. Try middle point each time;

3. The range is from the last house, which can't be lightened to 2 * radius, so the farthest point can be lightened is right = nums[idx] + 2 * r.

Implementation

const int lights = 3;
const double eps = 1e-6;
int canLitUp(vector<int>& nums, double r) {
    int right = -1, count = 0;
    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] > right) {
            count++;
            right = nums[i] + 2 * r;
        }
    }
    return count <= lights;
}

double solve(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    double l = 0, r = nums.back() - nums[0];
    while (r - l > eps) {
        double mid = (l + r) / 2;
        if (canLitUp(nums, mid))
            r = mid;
        else
            l = mid;
    }
    return r;
}

Time Complexity

• Time: O(nlogn)
• Space: O(1)