Heaters

题目来源
有n个房子，n个加热器，问加热器加热范围半径得多大才可以覆盖所有房子。
我一开始用暴力做法，找出每个房子离哪个加热器最近，然后记录下来，最后求一下哪个房子离所有的加热器最远，就是我们想要的结果。
代码如下：

class Solution {
public:
    int findRadius(vector<int>& houses, vector<int>& heaters) {
        int n1 = houses.size(), n2 = heaters.size(), res = 0;
        for (int i=0; i<n1; i++) {
            int minDis = INT_MAX;
            for (int j=0; j<n2; j++) {
                minDis = min(minDis, abs(heaters[j] - houses[i]));
            }
            res = max(minDis, res);
        }
        return res;
    }
};

然后就超时了…看了下tags，用二分，然后就AC了，注意这俩数组不是有序的…我以为是有序的，搞了半天…

class Solution {
public:
    int findRadius(vector<int>& houses, vector<int>& heaters) {
        int n1 = houses.size(), n2 = heaters.size(), res = 0;
        sort(houses.begin(), houses.end());
        sort(heaters.begin(), heaters.end());
        for (int i=0; i<n1; i++) {
            int minDis = INT_MAX;
            int l = 0, r = n2 - 1;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (heaters[mid] == houses[i]) {
                    minDis = 0;
                    break;
                }
                else if (heaters[mid] < houses[i]) {
                    l = mid + 1;
                    minDis = min(minDis, houses[i] - heaters[mid]);
                }
                else {
                    r = mid - 1;
                    minDis = min(minDis, heaters[mid] - houses[i]);
                }
            }
            res = max(minDis, res);
        }
        return res;
    }
};