C++ easy solution with explanation


  • 0

    sort heaters first
    find the closest heater for each house by binary search.

    class Solution {
    public:
        int findRadius(vector<int>& houses, vector<int>& heaters) {
            int res = 0;
            sort(heaters.begin(), heaters.end());
            for (auto i : houses) {
                auto it = lower_bound(heaters.begin(), heaters.end(), i);
                if (it == heaters.end()) { // last heater
                    it--;
                } else if (it != heaters.begin()) { // prev heater might be closer, example: heater: 1,3,9 and house 4
                    auto cur = it;
                    it--;
                    if (abs(*cur - i) < abs(*it - i))
                        it = cur;
                }
                res = max(res, abs(*it - i));
            }
            return res;
        }
    };
    

Log in to reply
 

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