【二分】供暖器半径

供暖器

冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。

在加热器的加热半径范围内的每个房屋都可以获得供暖。

现在，给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置，请你找出并返回可以覆盖所有房屋的最小加热半径。

说明：所有供暖器都遵循你的半径标准，加热的半径也一样。

二分搜索半径

最开始的想法，能否覆盖随半径是单调的，但这样在每次循环中仍需要搜索下一个没被覆盖的房子，所以最终时间复杂度是\(O(n\log^2n)\)。

所以并不是能二分就一定二分...下面的贪心更简单。

class Solution {
public:
    int findRadius(vector<int>& houses, vector<int>& heaters) {
        sort(houses.begin(), houses.end());
        sort(heaters.begin(), heaters.end());
        // O(nlogn)
        auto check = [&](int m) {
            int next = 0;
            for (int i = 0; i < heaters.size(); i++) {
                int h = heaters[i];
                if (h - m > houses[next]) return false;
                next = upper_bound(houses.begin(), houses.end(), h + m) - houses.begin();
                if (next == houses.size()) return true;
            }
            return false;
        };
        // O(nlog^2n)
        int l = 0, r = max(houses.back(), heaters.back()) - houses[0] + 1;
        while (l <= r) {
            int m = (l + r) / 2;
            if (check(m)) r = m - 1;
            else l = m + 1;
        }
        return l;
    }
};

贪心，记录每个房子的最近供暖器

更直接的做法，直接遍历房子，同时记录最近的供暖器即可，时间复杂度\(O(n\log n)\)（排序）

class Solution {
public:
    int findRadius(vector<int>& houses, vector<int>& heaters) {
        sort(houses.begin(),houses.end());
        sort(heaters.begin(),heaters.end());
        int ans = 0;
        int h = 0;
        // O(n)
        for (int i=0;i<houses.size();i++){
            while (h + 1 < heaters.size() && 
                   abs(houses[i] - heaters[h]) >= abs(houses[i] - heaters[h + 1])) h++;
            ans = max(ans,abs(houses[i]-heaters[h]));
        }
        return ans;
    }
};