475. 供暖器

雙指針

建立兩個指針，一個指向houses，一個指向heaters，並將兩個數組排序，方便後面配對。
$\begin{aligned} houses & = [1,2,3,4] \\ heaters & = [1,4] \end{aligned}$， 對於第一個房子houses[0]來說，先看看它跟哪個供暖器配對最好，
由於事先有排序，最近的兩個供暖器是heaters[0]，heaters[1]兩個，
在這兩個供暖器當中選擇距離比較短的那個。這個距離就是這間房子需要的「最小供暖器半徑」。
對每個房子都這樣做，將半徑取最大值，就是答案。

class Solution {
private:
    bool best(vector<int>& houses, vector<int>& heaters, int i, int j) {
        // houses[i] 跟 heaters[j] 配對是不是最好的選擇？
        // 對於 houses[i] 來說，可以配對的有左邊跟右邊兩個供暖器
        // 如果沒有右邊，那就只能選這一個：j == heaters.size() - 1
        // 如果兩邊都有，那麼看自己跟左邊這台的距離是不是比較近，比較近代表是最好的選擇
        return j == heaters.size() - 1 || abs(heaters[j] - houses[i]) < abs(heaters[j + 1] - houses[i]);
    }
public:
    int findRadius(vector<int>& houses, vector<int>& heaters) {
        ranges::sort(houses);
        ranges::sort(heaters);
        int res = 0;
        for(int i = 0, j = 0; i < houses.size(); i++) { // i 是 houses 的下標, j 是 heaters 的下標
            while(!best(houses, heaters, i, j)) {
                // 當 houses[i] 跟 heaters[j] 不是最佳配對時, 
                // 代表最佳配對的供暖器在後面
                j++;
            }
            res = max(res, abs(heaters[j] - houses[i]));
        }
        return res;
    }
};

二分查找

這個題目可以用二分查找，同樣用了都是用了兩個指針。

1. 一開始先排序數組，方便後續判斷指定的半徑，能否讓供暖器覆蓋到所有的房屋。
2. 用二分查找找到滿足條件的最小半徑。

• 在判斷半徑是否能覆蓋所有房子的時候，先得到供暖器的左右邊界，再把範圍內的房子標記為可覆蓋。

class Solution {
public:
    int findRadius(vector<int>& houses, vector<int>& heaters) {
        ranges::sort(heaters);
        ranges::sort(houses);
        
        auto canCover = [&](int radius) -> bool {
            int n = houses.size();
            vector<bool> covered(n, false); // 為每個房子標記能否被覆蓋
            int l, r;
            int i = 0;
            for(int x : heaters) {
                l = x - radius;
                r = x + radius;
                for(; i < n; i++) {
                    if(l <= houses[i] && houses[i] <= r) {
                        covered[i] = true;
                    }
                    else {
                        break;
                    }
                }
            }
            for(i = 0; i < n; i++) {
                if(!covered[i]) {
                    return false;
                }
            }
            return true;
        };
        
        int left = 0, right = INT_MAX / 2;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(canCover(mid)) { // 半徑設定為 mid 可以覆蓋所有房子
                right = mid - 1; // 比 mid 還要大的半徑就不需要考慮了
            }
            else {
                left = mid + 1; // 無法覆蓋所有房子，比 mid 還要小的半徑就不需要考慮了。
            }
        }
        return left;
    }
};

複雜度分析

• 時間複雜度：$O(n\log{n} + m\log{m})$
• 空間複雜度：$O(1)$