力扣475.供暖器

力扣475.供暖器

• 二分答案

  • 排序之后双指针从前往后对每一个房子做判断

•   class Solution {
    public:
        int findRadius(vector<int>& houses, vector<int>& heaters) {
            int n = houses.size(),m = heaters.size();
            ranges::sort(houses);
            ranges::sort(heaters);
            auto check = [&](int r) -> bool
            {
                for(int i=0,j=0;i<n;i++)
                {
                    while(j<m && houses[i] > heaters[j] + r) j++;
                    if(j<m && heaters[j] - r <= houses[i] && houses[i] <= heaters[j] + r) continue;
                    return false;
                }
                return true; 
            };
            int l = 0,r = (int)1e9;
            while(l<r)
            {
                int mid = l + r >> 1;
                if(check(mid)) r = mid;
                else l = mid + 1;
            }
            return r;
        }
    };