1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <iostream>
#include <vector>
#include <algorithm>

class Solution {
public:
    int findRadius(std::vector<int>& houses, std::vector<int>& heaters) {
        std::sort(heaters.begin(), heaters.end());
        int n = heaters.size();
        int max_dist = 0, dist;
        for (int house : houses) {
            int j = std::lower_bound(heaters.begin(), heaters.end(), house) - heaters.begin();
            dist = 0x3fff'ffff;
            if (j < n) {
                dist = heaters[j] - house;
            }
            if (j) {
                dist = std::min(dist, house - heaters[j - 1]);
            }
            max_dist = std::max(dist, max_dist);
        }
        return max_dist;
    }
};