Easy to understand C++ solution with vanilla binary search & STL lower_bound


  • 0
    C

    Well the idea is same as most of the other solutions.

    1. Sort the heater array
    2. For each house, get its left and right bounds 'pair' from the heaters array. For each house take the min of the pair(because the the closest heater is sufficient to heat the house, other heater can be discarded). Maximize this value for all houses.
    class Solution {
    public:
        pair<int,int> binsearch(int key, vector<int> &v) {
            //skip searching the array if the key is out of bounds
            if(key < v[0])
                return make_pair(INT_MAX, v[0] - key);
            else if(key > v.back())
                return make_pair(key - v.back(), INT_MAX);
            //else search
            int l = 0, r = v.size() - 1;
            while(l < r) {
                int m = l + ((r-l) >> 1);
                if(key > v[m])
                    l = m + 1;
                else
                    r = m;
            }
            return v[l] == key ? make_pair(0,0) : make_pair(key - v[l-1], v[l] - key);
        }
        int findRadius(vector<int>& houses, vector<int>& heaters) {
            //if there is no house
            if(!houses.size())
                return 0;
            //if there is no heater
            if(!heaters.size())
                return INT_MAX;
            sort(heaters.begin(), heaters.end());
            int ret = 0;
            for(auto h : houses) {
                auto lr = binsearch(h, heaters);
                ret = max(ret, min(lr.first, lr.second));
                
                /*remove this comment & comment out previous two lines if using library function is preferred(it takes more time)
                auto lb = lower_bound(heaters.begin(), heaters.end(), h);
                if(lb == heaters.begin())
                    ret = max(ret, *lb - h);
                else if(lb == heaters.end())
                    ret = max(ret, h - heaters.back());
                else
                    ret = max(ret, min(*lb - h, h - *(lb - 1)));
                */
            }
            return ret;
        }
    };
    

Log in to reply
 

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