题目描述

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

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

所以，你的输入将会是房屋和供暖器的位置。你将输出供暖器的最小加热半径。

说明

• 给出的房屋和供暖器的数目是非负数且不会超过 25000。
• 给出的房屋和供暖器的位置均是非负数且不会超过 10^9。
• 只要房屋位于供暖器的半径内（包括在边缘上），它就可以得到供暖。
• 所有供暖器都遵循你的半径标准，加热的半径也一样。

样例

输入：[1,2,3],[2]
输出：1
解释：仅在位置 2 上有一个供暖器。如果我们将加热半径设为 1，那么所有房屋就都能得到供暖。

输入：[1,2,3,4],[1,4]
输出：1
解释：在位置 1 和 4 上有两个供暖器。我们需要将加热半径设为 1，这样所有房屋就都能得到供暖。

算法1

(二分答案) $O(n \log n + m \log m + (n + m) \log L)$

1. 将房屋和暖气的位置分别从小到大排序。
2. 假设得到了加热半径 $r$，即可在 $O(n + m)$ 的时间内，判断是否所有的房屋都得到了暖气，具体为，逐一枚举房屋，然后判断是否有暖气覆盖，由于房屋和暖气的坐标都是单调的，所以第 $i+1$ 个房屋不会使用坐标小于第 $i$ 个房屋的暖气位置。
3. 加热半径也是单调的，故可以使用二分来加速寻找最小的半径。

时间复杂度

• 排序的时间复杂度为 $O(n \log n + m \log m)$，二分判定的时间复杂度为 $O((n + m) \log L)$，其中$L$为最大房屋或暖气的坐标。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:

    bool check(int r, const vector<int>& houses, const vector<int>& heaters) {
        int n = heaters.size();
        for (int i = 0, j = 0; i < houses.size(); i++) {
            while (j < n && abs(houses[i] - heaters[j]) > r)
                j++;
            if (j == n)
                return false;
        }
        return true;
    }

    int findRadius(vector<int>& houses, vector<int>& heaters) {
        sort(houses.begin(), houses.end());
        sort(heaters.begin(), heaters.end());
        if (houses.size() == 0)
            return 0;

        int l = 0, r = max(*houses.rbegin(), *heaters.rbegin());
        while (l < r) {
            int mid = (l + r) >> 1;
            if (check(mid, houses, heaters))
                r = mid;
            else
                l = mid + 1;
        }

        return l;
    }
};

算法2

(贪心) $O(n \log n + m \log m)$

1. 将房屋和暖气的位置分别从小到大排序。
2. 逐一枚举每个房屋，对于房屋 $i$，他使用暖气必定是距离他左右（如果有）最近的两个之一，由于我们已经对坐标进行了排序，所以这个过程如算法 1 一样是单调的。
3. 按照 2 的过程，随时更新半径的最大值$r$即可。

时间复杂度

• 排序的时间复杂度为 $O(n \log n + m \log m)$，然后是线性扫描，每个位置最多被遍历一次，时间复杂度为 $O(n + m)$，故总时间复杂度为 $O(n \log n + m \log m)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int findRadius(vector<int>& houses, vector<int>& heaters) {
        int n = heaters.size();
        sort(houses.begin(), houses.end());
        sort(heaters.begin(), heaters.end());

        int r = 0;
        for (int i = 0, j = 0; i < houses.size(); i++) {
            if (abs(houses[i] - heaters[j]) > r) {

                while (j < n && heaters[j] < houses[i])
                    j++;

                if (j == n) {
                    r = max(r, houses[i] - heaters[j - 1]);
                    j--;
                } else if (j == 0) {
                    r = max(r, heaters[j] - houses[i]);
                } else {
                    if (houses[i] - heaters[j - 1] < heaters[j] - houses[i]) {
                        r = max(r, houses[i] - heaters[j - 1]);
                        j--;
                    } else
                        r = max(r, heaters[j] - houses[i]);
                }
            }
        }
        return r;
    }
};