【Leetcode】475. Heaters

题目地址：

https://leetcode.com/problems/heaters/description/

给定两个数组$A$和$B$，分别代表房屋的坐标和加热器的坐标，每个加热器$B[i]$能加热的范围为$[B[i]-x,B[i]+x]$，$x$对于所有加热器都是一样的。问半径最小是多少能使得所有房屋都能被加热。

可以二分答案，然后用双指针（假设两个数组都排好了序，那么可以关注每个加热器可以加热到的最后一个房屋，这个下标一定是单调增的）。代码如下：

class Solution {
    
 public:
  int findRadius(vector<int>& houses, vector<int>& heaters) {
    
    sort(houses.begin(), houses.end());
    sort(heaters.begin(), heaters.end());
    int l = 0, r = max(heaters[0] - houses[0], houses.back() - heaters[0]);
    while (l < r) {
    
      int mid = l + (r - l >> 1);
      if (check(mid, houses, heaters)) r = mid;
      else l = mid + 1;
    }

    return l;
  }

  bool check(int len, vector<int>& ho, vector<int>& he) {
    
    for (int i = 0, j = 0; i < he.size(); i++) {
    
      if (ho[j] < he[i] - len) return false;
	  while (j < ho.size() && abs(ho[j] - he[i]) <= len) j++;
      if (j == ho.size()) return true;
    }

    return false;
  }
};

时间复杂度$O(l_A\log l_A+l_B\log l_B+(l_A+l_B)\log \max \{B[0]-A[0],B[l_B-1]-A[0]\})$，空间$O(1)$。