供暖器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
 public:
  int findRadius(vector<int>& houses, vector<int>& heaters) {
    int r = 1e9, l = 0;
    sort(houses.begin(), houses.end());
    sort(heaters.begin(), heaters.end());
    while (l < r) {
      int mid = l + r >> 1;
      if (check(houses, heaters, mid)) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  }
  bool check(vector<int>& houses, vector<int>& heaters, int x) {
    int n = houses.size(), m = heaters.size();
    for (int i = 0, j = 0; i < n; i++) {
      // i 指向房子，j 指向加热器
      // 加热器没遍历完，且第 i 个房子在第 j
      // 个加热器的半径范围之外（右侧），考虑下个加热器
      while (j < m && houses[i] > heaters[j] + x) j++;
      // 如果第 i 个房子在第 j 个加热器的加热半径下，考虑下个房子
      if (j < m && heaters[j] - x <= houses[i] && houses[i] <= heaters[j] + x)
        continue;
      return false;
    }
    return true;
  }
};