796. Minimum Light Radius#

1
You are given a list of integers nums
2

3
representing coordinates of houses on a 1-dimensional line.
4

5
You have 3 street lights that you can put anywhere on the coordinate line
6

7
and a light at coordinate x lights up houses in [x - r, x + r],
8

9
inclusive. Return the smallest r required
10

11
such that we can place the 3 lights and all the houses are lit up.
12

13
Constraints
14

15
n ≤ 100,000 where n is the length of nums
16
Example 1
17
Input
18
nums = [3, 4, 5, 6]
19
Output
20
0.5
21
Explanation
22
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.

1
class Solution {
2
public:
3
    bool isvaild(double diameter, vector<int>& nums) {
4
        int n = nums.size();
5
        double l = 0, ans = 0;
6
        while (l < n)
7
        {
8
            l = upper_bound(nums.begin(), nums.end(), nums[l] + diameter) - nums.begin();
9
            ans++;
10
        }
11
        return ans <= 3 ? 1: 0;
12
    }
13

14
    double solve(vector<int>& nums) {
15
        sort(nums.begin(), nums.end());
16
        int n = nums.size();
17
        double l = 0;
18
        double r = nums[n - 1];
19
        while(l < r)
20
        {
21
            int diameter = l + (r - l) / 2;
22
            if(isvaild(diameter, nums)) r = diameter;
23
            else l = diameter + 1;
24
        }
25
        return l / 2;
26
    }
27
}