Competitive_Programming/LeetCode/Full_List/475.cpp at master · Ravi-Maurya/Competitive_Programming · GitHub

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
32
33
34
class Solution {
public:
    int binary_search(int val, vector<int> &heaters){
        int res = 0;
        int l = 0, r = heaters.size()-1;
        while(l<=r){
            int mid = l + (r-l)/2;
            if(heaters[mid]==val)
                return 0;
            else if(heaters[mid]<val)
                l = mid+1;
            else
                r = mid-1;
        }
        return min(heaters[l]-val, val - heaters[r]);
    }

    int findRadius(vector<int>& houses, vector<int>& heaters) {
        int res = 0;
        sort(heaters.begin(),heaters.end());
        for(auto& house: houses){
            if(house<=heaters.front()){
                res = max(res, heaters.front() - house);
                continue;
            }
            if(house>=heaters.back()){
                res = max(res, house - heaters.back());
                continue;
            }
            res = max(res, binary_search(house,heaters));
        }
        return res;
    }
};