Clear and simple C++ solution


  • 0
    K
    class Solution {
    private:
        int binary_last_less(vector<int>& heaters, int house) {
            int lo = 0, hi = heaters.size() -1, mid;
            while(lo < hi) {
                mid = lo + (hi - lo + 1)/2;
                if(heaters[mid] > house) hi = mid - 1;
                else lo = mid;
            }
            return lo;
        }
        int binary_fisrt_larger(vector<int>& heaters, int house) {
            int lo = 0, hi = heaters.size() -1, mid;
            while(lo < hi) {
                mid = lo + (hi - lo)/2;
                if(heaters[mid] >= house) hi = mid;
                else lo = mid + 1;
            }
            return lo;
        }
    public:
        int findRadius(vector<int>& houses, vector<int>& heaters) {
            sort(heaters.begin(), heaters.end());
            int maxRadius = 0;
            for(auto house : houses) {
                int lower = binary_last_less(heaters, house);
                int upper = binary_fisrt_larger(heaters, house);
                maxRadius = max(maxRadius, min(abs(house - heaters[lower]), abs(heaters[upper] - house)));
            }
            return maxRadius;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.