Another easy-understanding solution based on the binary search.


  • 0
    R

    This problem is really like the problem:
    https://community.topcoder.com/stat?c=problem_statement&pm=1901&rd=4650
    And the explanation is
    https://www.topcoder.com/community/data-science/data-science-tutorials/binary-search/

    Basic idea, I set the high bound as the highest range a heater could have, that is, the right-most heater or house of the road. And the low bound as 0, which is the case that all the heater are exactly locate on each house.
    Then we do the binary search to figure out if the mid satisfy the need. If it does, then we keep it in the binary search, and set h = m. if not, we need increase the low bound to m + 1.
    Then we will find the lowest range that satisfies our need.

    public class Solution {
        public int findRadius(int[] houses, int[] heaters) {
            if(heaters.length == 0 || houses.length == 0) return 0;
            Arrays.sort(houses);
            Arrays.sort(heaters);
            int l = 0;
            int h = Math.max(houses[houses.length-1], heaters[heaters.length-1]); 
            while(l<h){
                int m = (l + h) / 2;
                int j = 0;
                for(int i : heaters){
                    while(j < houses.length && (i - m) <= houses[j] && (i + m) >= houses[j]){
                        j++;
                    }
                }
                if(j == houses.length) h = m;
                else l = m + 1;
            }
            return l;
        }
    }
    

Log in to reply
 

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