Simple Linear Solution after sorting houses and heaters C++


  • 0
    S

    '''

    int findRadius(vector<int>& houses, vector<int>& heaters) {
        sort(heaters.begin(), heaters.end());
        sort(houses.begin(), houses.end());
        int i = 0, j = 0;
        int min_r;
        if(heaters[i] >= houses[j]) min_r = heaters[i] - houses[j];
        while(j < houses.size() && houses[j] <= heaters[i]) j++;
        i++;
        // first heater has to warm all the houses before it
        while(j < houses.size() && i < heaters.size()){
            while(j < houses.size() && houses[j] <= heaters[i]){
                min_r = max(min_r, min(abs(houses[j]-heaters[i-1]), abs(houses[j]-heaters[i])));
                // for all houses between two heaters, the heater closer to house would warm the house.
                j++;
            }
            i++;
        }
        if(i==heaters.size()){
            min_r = max(min_r, houses[houses.size()-1]-heaters[heaters.size()-1]);
            // last heater has to warm all the houses after it.
        }
        return min_r;
    }
    

    '''


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.